高效处理区间查询与修改的数据结构
线段树是一种二叉树结构，将数组分段存储，支持：
时间复杂度：查询和修改均为 $$ O(\log n) $$
const int MAXN = 1 << 18;
int tree[MAXN * 4], a[MAXN];
// 建树
void build(int p, int l, int r) {
if (l == r) {
tree[p] = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
tree[p] = tree[p * 2] + tree[p * 2 + 1]; // 区间和
}
// 区间查询
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[p];
if (qr < l || r < ql) return 0; // 不相交
int mid = (l + r) / 2;
return query(p * 2, l, mid, ql, qr) +
query(p * 2 + 1, mid + 1, r, ql, qr);
}
// 单点修改
void update(int p, int l, int r, int pos, int val) {
if (l == r) {
tree[p] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(p * 2, l, mid, pos, val);
else update(p * 2 + 1, mid + 1, r, pos, val);
tree[p] = tree[p * 2] + tree[p * 2 + 1];
}