专栏文章

P3368 【模板】树状数组 2 题解

FFish_egg_
P3368题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mipsylgk
此快照首次捕获于
2025/12/03 17:26
3 个月前
此快照最后确认于
2025/12/03 17:26
3 个月前
查看原文
树状数组是一种支持单点修改，区间查询的精巧的数据结构，通常用于维护满足结合律和可差分的运算和信息。又称二叉索引树（Binary Index Tree）、Fenwick Tree。

原理介绍\color{00cd00}\text{原理介绍}

下面这张图展示了树状数组的原理（来源：OI-Wiki）。
其中 cxc_x 表示以 xx 为右端点，长度为 lowbit(x){\rm lowbit}(x) 的区间的和。
lowbit(x){\rm lowbit}(x) 表示的是 xx 在二进制表示下，最低位的 11 的权值。
例如，1010 在二进制表示下为 101▲010\underset{\blacktriangle}{\bf1}0，加粗的就是最低位的 11，它的权值是 22，因此 lowbit(10)=2\rm lowbit(10)=2。
再例如，2424 在二进制表示下为 11▲0001\underset{\blacktriangle}{\bf1}000，最低位的 11 的权值为 88，因此 lowbit(24)=8\rm lowbit(24)=8。
根据位运算知识，可以得到 lowbit(x) = x & -x，其中 & 为按位与运算。
如果一个数减去自己的 lowbit\rm lowbit，得到的数再减去自己的 lowbit\rm lowbit，不断重复，最终这个数一定会变成 00。
例如 7(111)⟶ ⁣−16(110)⟶ ⁣−24(100)⟶ ⁣−407(111)\overset{\!-1}{\longrightarrow}6(110)\overset{\!-2}{\longrightarrow}4(100)\overset{\!-4}{\longrightarrow}0。
那么我们要计算 a1…7a_{1\dots7} 的和，就只需要求 c7+c6+c4c_7+c_6+c_4 即可。观察上图，看看是不是这样。
由此我们可以得到查询 a1…xa_{1\dots x} 的代码：
CPP
int query(int x)
{
	int ans = 0;
	while(x > 0)
	{
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}
可以发现，树状数组通过将一段数划分成 O(log⁡n)O(\log n) 段数的和，从而能够实现高效的查询操作。
如果要求任意一段区间 al…ra_{l\dots r} 的和，可以借助前缀和的思想，用 a1…ra_{1\dots r} 的和减去 a1…l−1a_{1\dots l-1} 的和，即 query(r) - query(l-1)。这也说明树状数组可以当成一个支持修改的前缀和来用。
如果要将 a5a_5 加上一个数 kk 该如何处理？观察包含 a5a_5 的区间，只有 c5c_5，c6c_6 和 c8c_8。那么就只需要将 c5c_5，c6c_6 和 c8c_8 都加上 kk 即可。而 6=5+lowbit(5)6=5+\rm lowbit(5)，8=6+lowbit(6)8=6+\rm lowbit(6)。也就是说，在树状数组中，一个结点 xx 的父亲是 x+lowbit(x)x+{\rm lowbit}(x)。由此我们可以得到将 axa_x 加上 kk 的代码：
CPP
void update(int x, int k)
{
	while(x <= n)
	{
		c[x] += k;
		x += lowbit(x);
	}
}
显然，修改操作的时间复杂度也为 O(log⁡n)O(\log n)。
但是在本题中，我们需要实现的是区间修改，单点查询，怎么办？借助差分的思想。定义差分数组 di=ai−ai−1d_i = a_i - a_{i-1}。于是有 ax=∑i=1xdia_x = \sum\limits_{i=1}^x d_i。如果要在 al…ra_{l\dots r} 加上 kk，只需要让 dl←dl+k,dr+1←dr+1−kd_l\gets d_l+k,d_{r+1}\gets d_{r+1}-k。使用树状数组维护这一过程即可。

代码实现\color{00cd00}\text{代码实现}

树状数组的模板部分和 P3374 是完全一样的。
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
struct BIT{ //树状数组维护差分数组
	int c[N], lowbit(int x){return x & -x;}
	void update(int x, int k){while(x < N) c[x] += k, x += lowbit(x);}
	int query(int x){int s = 0; while(x) s += c[x], x -= lowbit(x); return s;}
} t;
int n, m, a[N];
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i], t.update(i, a[i] - a[i-1]);
	while(m --> 0){
		int op, x, y, k; cin >> op;
		if(op == 1) cin >> x >> y >> k, t.update(x, k), t.update(y + 1, -k);
		if(op == 2) cin >> x, cout << t.query(x) << "\n";
	}
	return 0;
}
推荐继续阅读我的 树状数组小记，包含更多树状数组的高级应用。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...