【笔记】树状数组

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

根据仍以正整数关于

2

的不重复次幂的唯一分解性质，可以尝试按照二进制拆分，具体如下：

若一个正整数

x

可以被“二进制分解”成

x=2^{i1}+2^{i2}+\cdots+2^{im}

，其中

i1>i2>\cdots>im

，则可以将

[1,x]

分解为不超过

\lceil \log_x\rceil

个小区间：

长度为 $2^{i1}$ 的小区间 $[1,2^{i1}]$
长度为 $2^{i2}$ 的小区间 $[2^{i1}+1,2^{i1}+2^{i2}]$
$\cdots$
长度为 $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，所以还可以进一步简化。

CPP

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

。

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

CPP

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

的叶节点）向根节点的路径修改即可，直到跳到数组长度之外为止。

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

CPP

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

文章操作