问题 区间查询 单点修改

1. 快速求前缀和
2. 修改某一个数

要求时间复杂度$O(log n)$
数组和前缀和数组都不能达到这个要求。

基本原理

由高到低
$$x=2^a+2^b+2^c…+2^z, a<=log x$$

区间拆分：
$$(x-2^z,x]$$
$$(x-2^z-2^y,x-2^z]$$
$$…$$
$$(0,x-2^z-2^y-…-2^b]$$

$(L,R]$区间的长度一定是$R$的二进制表示的最后一位 $1$
9=8+1 1001
(8,9]
(0,8]

c[x]=a[x-lowbit(x)+1,x] 以 $x$ 结尾，长度是 $2^k$ 的区间和( $k$ 是 $x$ 末尾 $0$ 的个数)

父节点找子节点：x,x-lowbit(x);
子节点找父节点：修改子节点之后，父节点也要修改。$+lowbit(x)$

建立树状数组

for (int i = 1; i <= n; i++) {
    tr[i] = a[i];
    for (int j = i - 1; j > i - lowbit(i); j -= lowbit(j)) {
        tr[i] += tr[j];
    }
}

// 单点修改
void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i))  tr[i]+=c;
}
// 区间查询
int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tr[i];
    return res;
}