树状数组

树状数组定义

奇数上总是本元素 偶数会包含前面的元素

// 将C数组的下标i转化成二进制:
1=(001) C[1]=A[1];
2=(010) C[2]=A[1]+A[2];
3=(011) C[3]=A[3];
4=(100) C[4]=A[1]+A[2]+A[3]+A[4];
5=(101) C[5]=A[5];
6=(110) C[6]=A[5]+A[6];
7=(111) C[7]=A[7];
8=(1000) C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];

二进制最后一个 1 表示的是包含的项数 所以求取 lowbit 最低位

Lowbit 求取方法

方法1（易于理解）:

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

方法2（更简洁）:

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

树状数组操作

更新操作

直接就可以初始化

单点更新

函数定义

void update(int i, int val)//单点更新（影响多个C元素）

更新过程

{
    while (i <= n) {
        C[i] += val;
        i = lowbit(i);
    }
}
//由叶子节点向上更新C数组

说明: 更新（从小到大）是查询（从大到小）的逆过程

读取操作

求前缀和

int sum(int i)
//求区间[1,i]所有元素的和
{
    int ret = 0;
    while (i > 0) {
        ret += C[i];
        //从右往左区间求和
        i = lowbit(i);
    }
}
return ret;
}

区间查询 已经解决的问题： 在构造出树状数组C[i]的前提下，求前缀和(Easy!)； 如何进行区间查询？ sum(R) - sum(L-1) (更Easy!) 下一个问题：单点更新

求逆序对

方法一： 统计后面有几个1 O(n^2) 树状数组优化

差分树状数组（区间修改+单点查询）

单点查询

若原数组为 a[i]，设数组 d[i] = a[i] - a[i-1]（a[0] = 0），则可以通过求 d[i] 的前缀和实现单点查询 a[i]。

// 单点查询（因为差分，所以单点值即前缀和）
int ask(int p) {
    int res = 0;
    while (p) res += c[p], p -= p & -p;
    return res;
}

区间修改

当给区间 [l, r] 加上 x 的时候： - a[l] 与前一个元素 a[l-1] 的差增加了 x， - a[r+1] 与 a[r] 的差减少了 x。

根据 d[i] 数组的定义，只需给 d[l] 加上 x，给 d[r+1] 减去 x 即可。

// 单点更新‘差分’，为区间修改做准备（c是树状数组）
void add(int p, int x) {
    while (p <= n) c[p] += x, p += p & -p;
}

// 区间修改（通过两个端点的更新，实现区间修改的目的）
void range_add(int l, int r, int x) {
    add(l, x);
    add(r + 1, -x);
}

区间修改+区间查询

区间修改 + 区间查询

位置 $ p $ 的前缀和： \[ \sum_{i=1}^{p} a[i] = \sum_{i=1}^{p} \sum_{j=1}^{i} d[j] \]

在等式右侧，$ d[1] $ 被用了 $ p $ 次，$ d[2] $ 被用了 $ p-1 $ 次…… 于是可知： \[ \sum_{i=1}^{p} \sum_{j=1}^{i} d[j] = \sum_{i=1}^{p} d[i] * (p-i+1) = (p+1) * \sum_{i=1}^{p} d[i] - \sum_{i=1}^{p} d[i] * i \]

使用两个树状数组

区间修改

// 维护2个树状数组
void add(int p, int x) {
    for (int i = p; i <= n; i += i & -i)
        c1[i] += x, c2[i] += x * p;
}
// 区间修改（不变）
void range_add(int l, int r, int x) {
    add(l, x), add(r + 1, -x);
}

区间查询

int ask(int p) { //前缀和查询，即查询区间[1,p]的和
    int res = 0;
    for (int i = p; i != i & -i;)
        res += (p + 1) * c1[i] - c2[i];
    return res;
}
int range_ask(int l, int r) { //区间查询
    return ask(r) - ask(l - 1);
}