欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

差分详解+树状数组扩展

程序员文章站 2022-06-01 11:52:53
...

前言:现在还不是很懂,不过先把模板抄在这里把。
介绍一下差分,一个很简单的东西。
一、简介
已知数组a为1,2,1,5,7,4
那么差分数组1,1,-1,4,2,-3
差分详解+树状数组扩展
显然,差分数组就是当前项与前一项的差值。
容易得到,an就是差分数组的前n项和。
二、那么有什么便利的地方呢?
我们假想一下,现在要给1至4的区间每个数加上1,那么差分数组会变成什么样呢,模拟一下得
a数组2,3,2,6,8,5
差分数组2,1,-1,4,1,-3
可以看到,只有下标为1和5的地方发生了变化。
刚才我们说到,差分数组的前n项和就是an,那我们在差分数组的1处加1,在5处减1,那么1到4利用差分数组前缀和求an,an的值确实都加了1,当我们求a5以后的数的话,我们就不需要加1了,所以差分数组a5处减1.

这样,差分数组的前缀和仍然是an。

树状数组+差分

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,tree[500009];
ll lowbit(ll x){
	return x&(-x);
}
ll sumn(ll x){
	ll ans=0;
	while(x>0){
		ans+=tree[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(ll x,ll w){
	while(x<=n){
		tree[x]+=w;
		x+=lowbit(x);
	}
}
int main()
{
	cin>>n>>m;
	ll last=0,nows=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%ld",&nows);
		add(i,nows-last);
		last=nows;
	}
	for(int i=1;i<=m;i++)
	{
		ll mid,l,r,q;
		cin>>mid;
		if(mid==1)
		{
			cin>>l>>r>>q;
			add(l,q);
			add(r+1,-q);
		}
		else
		{
			cin>>l;
			cout<<sumn(l)<<endl;
		}
	}
}
相关标签: 我的模板类