树状数组
简介
树状数组是一种用于维护 \(n\) 个数的区间和的数据结构。
一般能用树状数组做的题，都可以使用线段树来做。相较于码量，树状数组的码量要比线段树少许多，不过相对应的，它所能实现的功能没有线段树多。
好的，不多说废话，下面进入正题。
操作
现在我们已知数列 \(a_i\)。
\(\text{lowbit}\)
\(\text{lowbit(x)}\) 表示 \(x\) 表示的二进制中最低的一位 \(1\) 所表示的数，举个例子：\(4\) 的二进制为 \(100_{(2)}\)，那么 \(\text{lowbit(4)} = 100_{(2)} = 4\)；\(12\) 的二进制为 \(1100_{(2)}\)，那么 \(\text{lowbit(12)} = 100_{(2)} = 4\)。
怎么求呢？我们知道 \(-x\) 的补码为 \(x\) 按位取反再 \(+1\)，大家可以自行举例模拟，会发现最低的一位 \(1\) 所表示的数其实就是 \(x \& (-x)\)。
Code:
int lowbit(int x) {
return x & (-x);
}
\(\text{lowbit}\) 是树状数组的核心操作，为后面的操作奠定了基础。
\(\text{区间查询}\)
我们令 \(tr_i = \sum_{j = i - \text{lowbit(i)} + 1}^{i} a_i\)
如上图，我们假设要求 \(a_l\) 到 \(a_r\)，可以将 \(tr_r\) 加入 \(res\)（query 的值），然后我们就需要求 \(a_l\) 到 \(a_{r - \text{lowbit(r)}}\)，再将 \(tr_{r - \text{lowbit(r)}}\) 加入 \(res\dots\)
以此类推，我们就可以得到以下操作。
Code:
int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(x) ) res += tr[i];
return res;
}
答案为 sum(y) - sum(x - 1)。
\(\text{单点查询}\)
与 \(\text{区间查询}\) 一样，只不过最后的答案变为了 sum(x)。
\(\text{单点修改}\)
修改与查询其实是反着来的，相对应的，\(a_i\) 改变了，\(a_{i + \text{lowbit(i)}}\) 也会跟着改变，那么可以得到以下代码。
Code:
int add(int x,int k) {
for (int i = x; i <= n; i += lowbit(x) ) tr[i] += k;
}
\(\text{区间修改}\)
这时一定有人会有疑问：单点修改这么做，那区间修改呢？
其实非常简单，假设我们要修改 \(a_l\) 到 \(a_r\)，那么我们可以先将 \(a_l\) 到 \(a_n\) 加上 \(k\)，再将 \(a_{r + 1}\) 到 \(a_n\) 减去 \(k\)，即为我们将 \(a_l\) 到 \(a_r\) 都加上了 \(k\)。（此处以加 \(k\) 为例）
那么区间修改其实就是 add(x,k),add(y + 1,-k)。
Code
AC Code of P3374【模板】树状数组 1
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n,m;
int tr[N];
inline int read() {
int x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int lowbit(int x) {
return x & (-x);
}
int add(int x,int k) {
for (int i = x; i <= n; i += lowbit(i) ) tr[i] += k;
}
int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i) ) res += tr[i];
return res;
}
signed main() {
ios :: sync_with_stdio(false);
n = read();
m = read();
for (int i = 1; i <= n; ++ i ) add(i,read());
while (m -- ) {
int op = read(),x = read(),k = read();
if (op == 1) add(x,k);
else cout << sum(k) - sum(x - 1) << endl;
}
return 0;
}
AC Code of P3368【模板】树状数组 2
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int n,m;
int tr[N];
inline int read() {
int x = 0,f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int lowbit(int x) {
return x & (-x);
}
int add(int x,int k) {
for (int i = x; i <= n; i += lowbit(i) ) tr[i] += k;
}
int sum(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i) ) res += tr[i];
return res;
}
signed main() {
ios :: sync_with_stdio(false);
n = read();
m = read();
for (int i = 1; i <= n; ++ i ) {
int x = read();
add(i,x),add(i + 1,-x);
}
while (m -- ) {
int op = read(),x,y,k;
if (op == 1) {
x = read(); y = read(); k = read();
add(x,k);
add(y + 1,-k);
} else {
x = read();
cout << sum(x) << endl;
}
}
return 0;
}
写 blog 不易，请点个赞。
祝你理解树状数组。
作者：\(\text{songszh}\)