~~应该不会有人先做模板 $2$ 后做模板 $1$ 吧~~？

默认读者已经完成了【模板】树状数组

1

，所以本题解重点讲解差分部分。

前置知识

树状数组单点修改，区间查询。
差分思想。

思路

众所周知，树状数组是一种非常好写且高效的求前缀和的数据结构。普通的树状数组仅仅只支持单点修改。那么如果题目要求区间修改，单点查询，该怎么做呢？

修改

不难想到可以利用差分思想修改，即把树状数组看作差分数组。每次让区间

[l,r]

加上

v

时，只需要让下标为

l

，

l+\operatorname{lowbit}(l)

等处加上

v

，让

r+1

，

r+1+\operatorname{lowbit}(r+1)

等处加上

-v

即可。

查询

查询第

i

个数的值时，正常查询到

i

的前缀和，便可以得出答案。

正确性和复杂度分析

这样为什么是正确的呢？

众所周知，只要对差分数组求一个前缀和，就可以还原出原数组。而树状数组就是用于求前缀和的数据结构。我们用构建差分数组的方式去构建树状数组，使得此时的树状数组同时具有差分数组和普通树状数组的性质。这样，求一遍前缀和便可以得出原数据。
仔细想想，这样做的本质就是用树状数组维护差分数组。

时间复杂度显然是

O(n\log{n})

。

代码

代码与普通树状数组相差不大，唯一有区别的就是 do_add 函数。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sta__[100], stalen;
inline ll read() {
	ll x = 0, f = 1;
	char ch;
	while ((ch = getchar()) < 48 || ch > 57)if (ch == '-')f = -1;
	while (ch >= 48 && ch <= 57)x = x * 10 + ch - 48, ch = getchar();
	return x * f;
}
inline void write (ll x, bool bo) {
	if (x < 0)putchar ('-'), x = -x;
	do sta__[++stalen] = x % 10, x /= 10;
	while (x);
	while (stalen)putchar (sta__[stalen--] + 48);
	putchar (bo ? '\n' : ' ');
}
const ll N = 500009;
ll tr[N];
ll n, m;
inline ll lowbit (ll x) {
	return x & (-x);
}
inline void add (ll pos, ll v) {
	while (pos <= n) {
		tr[pos] += v;
		pos += lowbit (pos);
	}
}
inline void do_add (ll k, ll y, ll x) { //差分思想修改
	add (x, k);
	add (y + 1, -k);
}
inline ll do_qu (ll pos) {
	ll res = 0;
	while (pos > 0) {
		res += tr[pos];
		pos -= lowbit (pos);
	}
	return res;
}
int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i++)
		do_add (read(), i, i);
	for (int i = 1; i <= m; i++) {
		ll op = read();
		if (op == 1)do_add (read(), read(), read()); //函数传参从右到左
		else write (do_qu (read()), 1);
	}
	return 0;
}

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

文章操作

前置知识

思路

修改

查询

正确性和复杂度分析

代码

相关推荐

评论

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