您的位置: 首页  >  IT文章  >  简单理解一维树状数组区间求和+修改

简单理解一维树状数组区间求和+修改

分类: IT文章 • 2024-02-18 10:16:01

FBI WARNING

在阅读前，请先弄懂单点修改+区间查询和区间修改+单点查询。

近日，本萌新在学习了树状数组后，在某度上寻找了各大大佬的区间修改+区间查询的博客。

发现了高一年级无法理解的奇怪的操作...

于是乎，在我的不懈努力（手动模拟）之下，终于弄懂了这个树状数组区间求和修改的奥♂义。

那么首先我们假设一个数组a，里面是我们的所有数。

让我们回忆一下区间修改需要干什么，对了！维护差分数组！

所以我们再来一个数组d，是我们数组a的差分数组。

所以a[i] = d[1] + d[2] + .. + d[i]; (下标从一开始)

因此我们只需要维护一个差分数组就可以了。

让我们再回忆一下区间查询该怎么做，对了！前缀和！

那么肯定有人要问了，我堂堂正正一个差分数组，前缀和怎么搞？

现在我们来看一下：

  • a[1] = d[1];

  • a[2] = d[1] + d[2];

  • a[3] = d[1] + d[2] + d[3];

  • a[4] = d[1] + d[2] + d[3] + d[4];

停！打住！够了。

假设我们要求sum[4] = a[1] + a[2] + a[3] + a[4]。

那么我们的式子就会变成;

sum[4] = d[1] + d[1] + d[2] + d[1] + d[2] + ........ + d[4];

超麻烦啊喂！

我们回去再看一看a[1] - a[4]那四行。这次我们竖着看。

有没有豁然开朗的赶脚！

sum[4] = d[1] ∗ 4 + d[2] ∗ 3 + d[3] ∗ 2 + d[4] ∗ 1;

接下来再看....

sum[4] = d[1] ∗ 4 + d[2] ∗ 3 + d[3] ∗ 2 + d[4] ∗ 1;

= (d[1] ∗ 5 + d[2] ∗ 5 + .. d[4] ∗ 5) - d[1] ∗ 1 + d[2] ∗ 2 + .. d[4] ∗ 4;

所以如果我们要求sum[i];

sum[i] = (i + 1)∗(d[1] + d[2] + .. d[i]) - (d[1]∗1 + d[2] ∗ 2 + .. d[i] ∗ i);

现在我们尝试将这个式子与前缀和联系起来:

看这个 (d[1] + d[2] + .. d[i])

这不是 d[i]的前缀和吗？！

再看这个 (d[1]∗1 + d[2] ∗ 2 + .. d[i] ∗ i)

如果我们考虑再弄一个数组d2。

d2[i] = d[i] * i;

带入一下 (d2[1] + d2[2] + .. d2[i])

就变成了d2的前缀和！

所以我们将a数组差分后放进d数组里，初始化d2[i] = d[i] * i

我们就可以弄两个树状数组，一个维护d，一个维护d2

接下来放 P3372的代码。大家也可以去做一下（用树状数组哦）

首先需要这俩

LL d_tr[100005],d2_tr[100005]; // 分别是维护d和d2的树状数组

这是更新操作

void add(int x,LL v) // 在x的位置加上v
{
	for(int i = x;i <= n;i += lowbit(i)){
		d_tr[i] += v;
		d2_tr[i] += x * v;
	} 
	// 因为 d2_tr[x] += d_tr[x] * x;
	// d_tr[x] += v;所以我们要更新d2_tr[x] = (d_tr[x] + v) * x;
	// 就相当于 d2_tr[x] += x * v;
	// 然后向上更新 
	// 循环中的i是用来代替向上更新的x的,不懂得可以手动模拟一下~ 
}

这是查询

LL sum(int x) // 查询前缀和
{
	long long ans = 0;
	for(int i = x;i > 0;i -= lowbit(i)){
		ans += (x+1) * d_tr[i] - d2_tr[i];
	}
	// 根据我们推出来的东西求前缀和
	// 不懂的话，手动模拟依旧是个好办法 
	return ans;
}

输入时的初始化

for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
		add(i,a[i] - a[i-1]); // 将差分后的值放入树状数组 
	}

主函数中的更新记得写成这样

	add(x,v);		//区间更新操作，差分的知识 
	add(y+1,-v);

主函数中的查询记得写成这样

	LL ans = sum(y) - sum(x-1);	//前缀和之差算区间和 
	printf("%lld
",ans);

总代码

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
LL a[100005],n,m;
LL d_tr[100005],d2_tr[100005]; // 分别是维护d和d2的树状数组 

int lowbit(int x){
	return x & (-x);
}

void add(int x,LL v) // 在x的位置加上v
{
	for(int i = x;i <= n;i += lowbit(i)){
		d_tr[i] += v;
		d2_tr[i] += x * v;
	} 
	// 因为 d2_tr[x] += d_tr[x] * x;
	// d_tr[x] += v;所以我们要更新d2_tr[x] = (d_tr[x] + v) * x;
	// 就相当于 d2_tr[x] += x * v;
	// 然后向上更新 
	// 循环中的i是用来代替向上更新的x的,不懂得可以手动模拟一下~ 
}

LL sum(int x) // 查询前缀和 主函数里要写成sum(y) - sum(x-1);
{
	long long ans = 0;
	for(int i = x;i > 0;i -= lowbit(i)){
		ans += (x+1) * d_tr[i] - d2_tr[i];
	}
	// 根据我们推出来的东西求前缀和
	// 不懂的话，手动模拟依旧是个好办法 
	return ans;
}

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i = 1;i <= n;i++){
		scanf("%lld",&a[i]);
		add(i,a[i] - a[i-1]); // 将差分后的值放入树状数组 
	}
	while(m--){
		LL v;
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op == 1){
			scanf("%lld",&v);
			add(x,v);		//区间更新操作，差分的知识 
			add(y+1,-v);
		}
		else {
			LL ans = sum(y) - sum(x-1);	//前缀和之差算区间和 
			printf("%lld
",ans);
		}
	}
	return 0;
}

相关推荐