树状数组

建立数组$c$，其中$c[x]$保存序列$a$的区间$[x - lowbit(x) + 1, x]$中所有数的和

满足性质：

1. 每个内部节点$c[x]$保存以它为根的子树中多有叶节点的和
2. 每个内部节点$c[x]$的子节点的个数等于$lowbit(x)$的位数
3. 除树根外，每个$c[x]$的父节点是$c[lowbit(x) + x]$
4. 树的深度为$O(\log N)$

基本操作：

1. 快速求前缀和$O(\log n)$

// 查询序列a第1-x个数的和，求a[l - r]的和即为ask(r) - ask(l - 1)
int ask(int x)
{
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
}

1. 修改某个数$O(\log n)$

// 给序列中一个数a[x]加上y
void add(int x, int y)
{
    for (; x <= N; x += x & -x) c[x] += y;
}

建树方式：
1. $O(n \log n)$方式，每次$add(i, a[i])$
2. $O(n)$方式

// 方式1
void build() 
{
    for (int i = 1; i <= n; i++) 
    {
        tr[i] += a[i];

        // 获得父节点下标
        int fa = i + lowbit(i); 
        // 判断父节点是否超出数列范围
        if (fa <= n) tr[fa] += tr[i];
    }
}

// 方式2
c[x] = s[x] - s[x - lowbit(x)]

拓展基本操作：

将原数组改用差分数组加入到树状数组

1. 修改区间值$O(\log n)$

区间[l, r]都加d
add(l, d), add(r + 1, -d);

1. 查询某个数$O(\log n)$ ask(x)