【笔记】树状数组

· · 算法·理论

树状数组可以高效率地查询和维护数列的前缀和（或区间和），支持单点修改和区间查询。

根据仍以正整数关于 2 的不重复次幂的唯一分解性质，可以尝试按照二进制拆分，具体如下：

若一个正整数 x 可以被“二进制分解”成 x=2^{i1}+2^{i2}+\cdots+2^{im}，其中 i1>i2>\cdots>im，则可以将 [1,x] 分解为不超过 \lceil \log_x\rceil 个小区间：

  1. 长度为 2^{i1} 的小区间 [1,2^{i1}]
  2. 长度为 2^{i2} 的小区间 [2^{i1}+1,2^{i1}+2^{i2}]
  3. \cdots
  4. 长度为 2^{im} 的小区间 [2^{i1}+2^{i2}+\cdots+2^{im-1}+1,2^{i1}+2^{i2}+\cdots+2^{im}]

其中，若区间结尾为 R，则区间长度为 R 的二进制分解下最小的 2 的次幂，即 lowbit(R)。

由二进制得 lowbit(x)=x&(~x+1)=x&(-x)。因为取反后，末尾的所有 0 变为 1，最低位的 1 变为了最低位的 0，此时再对其加 1，会一直向前进位，直至最低位的 0，此时再进行按位与，自然只有最低位的 1 被保留。当然，因为补码情况下 -x=~x+1，所以还可以进一步简化。

int lowbit(int x) {return x&(-x);}
int main()
{
  cin >> x;
  for (int i = x; i; i -= lowbit(i))
    //分成的每一个区间为 [i-lowbit(i)+1, i]
}

树状数组基于此，可以维护序列前缀和。对于给定的序列 a，我们令数组 c 的第 x 项 c_x 保存序列 a 的区间 [x-lowbit(x)+1,x] 中的所有数之和，即 c_x=\sum^x_{i=x-lowbit(x)+1}a_i。

由此，我们写出树状数组的查询前缀和代码。

ll query(int x)
{//查询[1,x]区间和
  ll ans=0;
  for(;x>0;x-=x&(-x)) ans += a[x]; //拆区间，计算和
  return ans;
}

事实上，树状数组中，结点 x 的父亲为 x+lowbit(x)。因此在单点修改中，我们只需要沿着单点（仅管理 a_x 的叶节点）向根节点的路径修改即可，直到跳到数组长度之外为止。

由此写出树状数组的单点修改代码。

void add(int x, int y)
{//将 a[x] 加上 y
  for (;x<=n;x+=x&(-x)) a[x]+=y;//不断修改更新并跳向父亲，直至超出数组长度n
}