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

树状数组是单点修改、区间查询，而这题是区间修改、单点查询，相当于动态的差分，维护差分数组就可以单点修改、区间查询。

设这个序列是

a

，它的长度是

n

，它的差分数组是

d

，即对于所有整数

j\in[2,n]

都有

d_j=a_j-a_{j-1}

，特别地

d_1=a_1

，显然

a_x=\sum\limits_{i=1}^x d_i

。

当执行操作

1

，区间

[x,y]

内每个数都加上

k

的时候，

d_x

加上

k

，

d_{y+1}

减去

k

（当

y=n

时不减）。

当执行操作

2

，要输出

a_x

的值时，输出

\sum\limits_{i=1}^n d_i

就好了。

d

用树状数组维护，时间复杂度

O(M\log N)

，空间复杂度

O(N)

，不会爆。

代码如下。

CPP

#include <iostream>
#define int long long
using namespace std;
int n,q,c[1000001];
void upd(int i,const int x) {
	for(;i<=n;i+=i&-i) c[i]+=x;
}
int query(int i) {
	int ret=0;
	for(;i;i-=i&-i) ret+=c[i];
	return ret;
}
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false),
	cout.tie(nullptr);
	cin>>n>>q;
	for(int a,i=1;i<=n;i++) {
		cin>>a;
		upd(i,a);
		upd(i+1,-a);
	}
	for(int op,l,r,x;q--;) {
		cin>>op;
		if(op==1) {
			cin>>l>>r>>x;
			upd(l,x);
			upd(r+1,-x);
		} else {
			cin>>x;
			cout<<query(x)<<'\n';
		}
	}
	return 0;
}

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

文章操作

相关推荐

评论

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