树状数组

树状数组是一种特殊的高效数据结构：时空复杂度和线段树类似，但是它的系数要小的多。树状数组是一个查询和修改复杂度都为 $log(n)$ 的数据结构，假设数组 $a_1,a_2\dots a_n$，那么查询 $\sum _{i=1}^n{a}_i$ 的时间复杂度是 $log$ 级别的，而且它是一个在线的数据结构，支持随时修改某一个元素的值，复杂度也是 $log$ 级别的。

树状数组的推导

若正整数 $x$ 的二进制表示为 $x=2^{i_1}+2^{i_2}+\cdots +2^{i_m}$，其中 $i_1>i_2>\cdots >i_m$，那么区间 $[1,x]$ 可以被分成 $O(log(x))$ 个区间，分别是

$1$：$[1,2^{i_1}]$

$2$：$[2^{i_1}+1,2^{i_1}+2^{i_2}]$

$\dots$

$m$：$[2^{i_1}+2^{i_2}+\cdots +2^{i_{m-1}}+1,2^{i_1}+2^{i_2}+\cdots +2^{i_m}]$。

它们的长度分别为 $2^{i_1},2^{i_2},\dots ,2^{i_m}$。

同时，我们发现如果区间以右端点 $R$ 结尾，则区间长度等于 $lowbit(R)$。

由此，区间 $[1,x]$ 可由以下代码分解为 $O(log(x))$ 个区间：

for (int i = x; i; i -= lowbit(i)) {
    // 区间 [i - lowbit(i) + 1, i]
	printf("[%d, %d]\n", i - lowbit(i) + 1, i);
}

而树状数组就是基于上述思想的一种数据结构，其基本用途就是维护序列的前缀和。

设数组 $c[x]$ 表示区间 $[x-lowbit(x)+1,x]$ 的和。如下图所示：

由上图我们可以推出：

1. $c[x]$ 的最后一个元素必是 $a[x]$。
2. $c[x]$ 的子节点个数为 $lowbit(x)$ 的位数。
3. 除树根外，$c[x]$ 的父节点为 $c[x+lowbit(x)]$。
4. 树的深度为 $O(log(N))$，其中 $N$ 为序列元素个数，当 $N$ 不是 $2$ 的整数次幂时，树状数组是一个森林结构。

两个基本操作

1. 查询前缀和

查询序列 $a$ 的前缀和，即 $a_1+a_2+\cdots +a_x$，按照上述分解区间的方法，我们应该求出 $x$ 的二进制表示中每个等于 $1$ 的位，把 $[1,x]$ 分成 $O(log(x))$ 个小区间，每个小区间的区间和已经保存在数组 $c$ 中，求和即可。

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}

如要查询区间 $[l,r]$ 的和，则计算 $query(r)-query(l-1)$ 即可。

2. 单点增加

单点增加即对序列 $a$ 的某一个元素 $a_x$ 加上 $y$，则要更新树状数组 $c$ 中所有包含 $a_x$ 的区间，即 $c[x]$ 及其所有祖先节点。

void add(int x, int y) {
    for (int i = x; i <= N; i += lowbit(i)) c[i] += y;
}

树状数组的初始化

初始 $c$ 数组全为 $0$，然后对序列 $a$ 中的每一个元素 $a_x$ 调用 $add(x,a_x)$ 即可。

树状数组的实际应用

1. 树状数组模板

洛谷 P3374. 【模板】树状数组 1

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
int a[N], c[N], n, m;

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

void add(int x, int y) {
	for (int i = x; i <= n; i += lowbit(i)) c[i] += y;
}

int sum(int x) {
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) res += c[i];
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		add(i, a[i]);
	}

	while (m --) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			add(x, y);
		} else {
			cout << sum(y) - sum(x - 1) << endl;
		}
	}

	return 0;
}

2. 求逆序对

AcWing 5910. 求逆序对

问题分析：

1. 在序列 $a$ 的取值范围上建立树状数组，初始全为 $0$。
2. 倒序扫描序列 $a$，对于 $a_x$，查询树状数组中 $[1,a_x-1]$ 的和，即 $query(a_x-1)$，即为 $a_x$ 的逆序对个数。
3. 更新树状数组，$add(a_x,1)$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], c[N], n;

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

void add(int x, int y) {
    for (int i = x; i <= N; i += lowbit(i)) c[i] += y;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += c[i];
    return res;
}


int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long res = 0;
    for (int i = n; i > 0; i--) {
        res += query(a[i] - 1);
        add(a[i], 1);
    }
    cout << res << endl;

    return 0;
}

如果序列 $a$ 的区间范围较大时，可以使用离散化，不过因为离散化本身就需要排序，此时不如使用归并排序求逆序对。

AcWing 241. 楼兰图腾

#include <bits/stdc++.h>
using namespace std;

const int N = 200010;
long long a[N], n, c1[N], c2[N], r1[N], r2[N], l1[N], l2[N];

void add(long long c[], long long x, long long y) {
    for (; x <= N; x += x & -x) {
        c[x] += y;
    }
}

long long query(long long c[], long long x) {
    long long ans = 0;
    for (; x; x -= x & -x) ans += c[x];

    return ans;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = n; i >= 1; i--) {
        r1[i] = query(c1, N) - query(c1, a[i]);
        add(c1, a[i], 1);

        r2[i] = query(c2, a[i] - 1);
        add(c2, a[i], 1);
    }

    memset(c1, 0, sizeof c1);
    memset(c2, 0, sizeof c2);

    for (int i = 1; i <= n; i++) {
        l1[i] = query(c1, N) - query(c1, a[i]);
        add(c1, a[i], 1);

        l2[i] = query(c2, a[i] - 1);
        add(c2, a[i], 1);
    }

    long long ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) {
        ans1 += r1[i] * l1[i];
        ans2 += r2[i] * l2[i];
    }
    cout << ans1 << " " << ans2 << endl;;

    return 0;
}

树状数组的扩展应用

1. 区间增加，单点查询

问题分析：结合差分的思想，维护指令的影响即可。

AcWing 242. 一个简单的整数问题

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, a[N], c[N];

void add(int x, int y) {
    for (; x <= N; x += x & -x) c[x] += y;
}

int query(int x) {
    int ans = 0;
    for (; x; x -= x & -x) ans += c[x];
    return ans;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (m--) {
        char op[2]; cin >> op;
        if (op[0] == 'Q') {
            int x; cin >> x;
            cout << a[x] + query(x) << endl;
        } else {
            int l, r, x; cin >> l >> r >> x;
            add(l, x);
            add(r + 1, -x);
        }
    }

    return 0;
}

2. 区间增加，区间查询

AcWing 243. 一个简单的整数问题 II

在上一题中，我们使用树状数组维护了一个数组 $b$，对于每条指令 C l r d，我们令 $b[l]+=d,b[r+1]-=d$，最后求 $b$ 的前缀和 $\sum _{i=1}^{x}b[i]$ 就可以得出经过这些指令之后 $a[x]$ 增加的值。那么序列 $a$ 的前缀和 $s$ 增加的值就是 $\sum _{i=1}^x\sum _{j=1}^{i}b[j]$。

上式可以改写为：

$$\sum _{i=1}^x\sum _{j=1}^{i}b[j]=\sum _{i=1}^x(x-i+1)\times b[i]=(x+1)\sum _{i=1}^{x}b[i]+\sum _{i=1}^{x}b[i]\times i$$

由此，在本题中我们维护两个树状数组 $c_0$ 和 $c_1$，$c_0$ 维护 $b[i]$ 的前缀和，$c_1$ 维护 $b[i]\times i$ 的前缀和。

对于 C l r d，我们令 $c_0[l]+=d,c_0[r+1]-=d,c_1[l]+=l\times d,c_1[r+1]-=(r+1)\times d$。

对于 Q l r d，我们令 $ans=(s[r]+(r+1)\times query(c_0,r)+query(c_1,r))-(s[l-1]+l\times query(c_0,l-1)-query(c_1,l-1))$。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
long long a[N], c[2][N], s[N];
int n, m;

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

long long query(int k, int x) {
    long long ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += c[k][i];
    return ans;
}

void add(int k, int x, int y) {
    for (int i = x; i <= n; i += lowbit(i)) c[k][i] += y;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    while (m--) {
        char op[2];
        int l, r, d;
        cin >> op >> l >> r;
        if (op[0] == 'Q') {
            long long ans = s[r] + (r + 1) * query(0, r) - query(1, r);
            ans -= s[l - 1] + l * query(0, l - 1) - query(1, l - 1);
            cout << ans << endl;
        } else {
            cin >> d;
            add(0, l, d);
            add(0, r + 1, -d);
            add(1, l, l * d);
            add(1, r + 1, -(r + 1) * d);
        }
    }

    return 0;
}

请同学们课后完成：

AcWing 244. 谜一样的牛