数据结构笔记 - 树状数组的区间操作

发表于 | 分类于 ，

哎呀！图片走丢了！

一般的树状数组只支持单点修改、单点查询和区间查询。其实树状数组也可以支持区间修改。最近做题遇到了这种用法，所以记录一下。

我们设原序列为$a_i$，再设$d_i=a_i-a_{i-1}$，这样就有：

所以：

所以：

这样，我们只要分别用树状数组维护$d_i$和$d_i\ast i$的前缀和即可。当我们要修改一个区间$[l,r]$时，只需要修改$l$和$r+1$两个点就行了（其实就是修改差分数组）。查询时只要求一下从$1$到$l-1$和从$1$到$r$的前缀和，然后相减就行了。

单点的操作其实就是长度为一的区间操作，照做就行了。

来看代码吧。

$Talk\ is\ cheap!Show\ me\ the\ code!$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void change(int pos,int data)
{
	for(int i=pos;i<=n;i+=lowbit(i))
	{
		c1[i]+=data;
		c2[i]+=pos*data;
	}
}
int get(int x)
{
	int ans=0;
	for(int i=pos;i>0;i-=lowbit(i))
		ans+=(x+1)*c1[i]-c2[i];
	return ans;
}
int query(int l,int r)
{
	int ans1,ans2;
	ans1=get(r);
	ans2=get(l-1);
	return ans1-ans2;
}
//正确的食用方法
{
	//单点修改
	change(i,data);
	change(i+1,-data);
	//区间修改
	change(l,data);
	change(r+1,-data);
	//单点查询
	res=query(pos,pos);
	//区间查询
	res=query(l,r);
}
0%