目前遇到树状数组的应用有

  1. 维护区间和(单点修改、区间修改查询)
  2. 任意区间最大值
  3. 求区间第k大(比主席树占用内存小，湘潭某题)