

树状数组

简介¶

树状数组和下面的线段树可是亲兄弟了，但他俩毕竟还有一些区别：
树状数组能有的操作，线段树一定有；
线段树有的操作，树状数组不一定有。

这么看来选择线段树不就 「得天下了」？

事实上，树状数组的代码要比线段树短得多，思维也更清晰，在解决一些单点修改的问题时，树状数组是不二之选。

原理¶

如果要具体了解树状数组的工作原理，请看下面这张图：

这个结构的思想和线段树有些类似：用一个大节点表示一些小节点的信息，进行查询的时候只需要查询一些大节点而不是更多的小节点。

最下面的八个方块就代表存入中的八个数，现在都是十进制。

他们上面的参差不齐的剩下的方块就代表的上级—— 数组。

很显然看出：
管理的是 &；
管理的是 &&&；
管理的是 &；则管理全部个数。

所以，如果你要算区间和的话，比如说要算 ~ 的区间和，暴力算当然可以，那上百万的数，那就 TLE 喽。

那么这种类似于跳一跳的连续跳到中心点而分值不断变大的原理是一样的（倍增）。

你从开始往前跳，发现（我也不确定是多少，算起来太麻烦，就意思一下）只管这个点，那么你就会找，发现管的是 &；那么你就会直接跳到，就会管 ~ 这些数，下次查询从往前找，以此类推。

用法及操作¶

那么问题来了，你是怎么知道管的的个数分别是多少呢？你那个个，个，个……是怎么来的呢？这时，我们引入一个函数——lowbit：

int lowbit(int x) {
  // 算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
  return x & -x;
}

lowbit 的意思注释说明了，咱们就用这个说法来证明一下：

发现第一个以及他后面的组成的二进制是

对应的十进制是，所以一共管理个。

这就是 lowbit 的用处，仅此而已（但也相当有用）。

你可能又问了：x & -x 是什么意思啊？

在一般情况下，对于 int 型的正数，最高位是 0，接下来是其二进制表示；而对于负数 (-x)，表示方法是把 x 按位取反之后再加上 1。

例如 :
；
；
。

那么对于 单点修改 就更轻松了：

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

每次只要在他的上级那里更新就行，自己就可以不用管了。

int getsum(int x) {  // a[1]……a[x]的和
  int ans = 0;
  while (x >= 1) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

区间加 & 区间求和¶

若维护序列的差分数组，此时我们对的一个前缀求和，即，由差分数组定义得

进行推导

区间和可以用两个前缀和相减得到，因此只需要用两个树状数组分别维护和，就能实现区间求和。

代码如下

int t1[MAXN], t2[MAXN], n;

inline int lowbit(int x) { return x & (-x); }

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

Tricks¶

建树：

每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。

// O(n)建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

查询第小/大元素。在此处只讨论第小，第大问题可以通过简单计算转化为第小问题。

参考 "可持久化线段树" 章节中，关于求区间第小的思想。将所有数字看成一个可重集合，即定义数组表示值为的元素在整个序列重出现了次。找第大就是找到最小的恰好满足

因此可以想到算法：如果已经找到满足，考虑能不能让继续增加，使其仍然满足这个条件。找到最大的后，就是所要的值。在树状数组中，节点是根据 2 的幂划分的，每次可以扩大 2 的幂的长度。令表示当前的所代表的前缀和，有如下算法找到最大的：

求出
计算
如果，则此时扩展成功，将累加到上；否则扩展失败，对不进行操作
将减 1，回到步骤 2，直至为 0

//权值树状数组查询第k小
int kth(int k) {
  int cnt = 0, ret = 0;
  for (int i = log2(n); ~i; --i) {      // i与上文depth含义相同
    ret += 1 << i;                      // 尝试扩展
    if (ret >= n || cnt + t[ret] >= k)  // 如果扩展失败
      ret -= 1 << i;
    else
      cnt += t[ret];  // 扩展成功后 要更新之前求和的值
  }
  return ret + 1;
}

时间戳优化：

对付多组数据很常见的技巧。如果每次输入新数据时，都暴力清空树状数组，就可能会造成超时。因此使用标记，存储当前节点上次使用时间（即最近一次是被第几组数据使用）。每次操作时判断这个位置中的时间和当前时间是否相同，就可以判断这个位置应该是 0 还是数组内的值。

//时间戳优化
int tag[MAXN], t[MAXN], Tag;
void reset() { ++Tag; }
void add(int k, int v) {
  while (k <= n) {
    if (tag[k] != Tag) t[k] = 0;
    t[k] += v, tag[k] = Tag;
    k += lowbit(k);
  }
}
int getsum(int k) {
  int ret = 0;
  while (k) {
    if (tag[k] == Tag) ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

例题¶

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：HeRaNO, Zhoier, Ir1d, Xeonacid, wangdehu, ouuan, ranwen, ananbaobeichicun, Ycrpro
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

树状数组

简介¶

原理¶

用法及操作¶

区间加 & 区间求和¶

Tricks¶

例题¶

评论