经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
树状数组1
来源:cnblogs  作者:嘛……  时间:2020/7/30 8:38:50  对本文有异议

树状数组1

基操:

void in(int x,int val)
{
	for(int i=x;i<=n;i+=(i&(-i)))  tr1[i]+=val;
} 

int ask(int x)
{
	int ans=0;
	for(int i=x;i;i-=(i&(-i)))	ans+=tr[i];
	return ans;
}

1,单点修改,区间查询:

for(int i=1;i<=n;i++)    in(a[i]);
in(x,val);
ask(r)-ask(l-1);

2.区间修改,单点查询:

差分;

for(int i=1;i<=n;i++)  in(i,a[i]-a[i-1]);
in(l,x),in(r+1,-x);
cout<<ask(r)<<endl;

3.区间修改,区间查询:

维护两个树状数组;

\(\displaystyle a[i]= \sum _{i=1}^{r}c[i]\)

\(\displaystyle \sum _{i=1}^{n}a[i]=\sum_{i=1}^{n} \sum_{j=1}^{i}c[i]=n \times c[1]+(n-1) \times c[2]+…+(n-(n-1)) \times c[n]=n \times \sum _{i=1}^{n}c[i]- \sum_{i=1}^{n}(i-1) \times c[i]\)

\(\displaystyle \sum _{i=l}^{r}=r \times \sum _{i=1}^{r}c[i]- \sum_{i=1}^{r}(i-1) \times c[i]-((l-1) \times \sum _{i=1}^{l-1}c[i]- \sum_{i-1}^{l-1}(i-1) \times c[i])\)

故一个维护前缀和,一个维护\(\sum(i-1)*c[i]\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;

#define ll long long

ll read()
{
	ll w=0,f=1;char ch;
	while(!(isdigit(ch=getchar())))    (ch=='-')&&(f=-f);
	for(w=(ch^48);isdigit(ch=getchar());w=(w<<1)+(w<<3)+(ch^48));
	return w*f;
}

const int N=1e6+10;
int n,q;
ll tr1[N],tr2[N];

void in(int x,ll val)
{
	for(int i=x;i<=n;i+=(i&(-i)))
	{
		tr1[i]+=val;
		tr2[i]+=(x-1)*val;
	}
} 

ll ask(int x)
{
	ll ans=0;
	for(int i=x;i;i-=(i&(-i)))	ans=ans+x*tr1[i]-tr2[i];
	return ans;
}

int main()
{
	scanf("%d%d",&n,&q);
	ll x,y=0;
	for(int i=1;i<=n;i++)   
	{
		x=read(); y=x-y;
		in(i,y);
		y=x;
	} 
	
	for(int i=1;i<=q;i++)
	{
		int opt=read();
		if(opt==1)	
		{
			int l=read(),r=read(),x=read();
			in(l,x),in(r+1,-x);//r+1处要减r*x。即-(x*(l-1)+x*(r-l+1)*x)
		}
		else  
		{
			int l=read(),r=read();
			printf("%lld\n",ask(r)-ask(l-1));
		}
	}
	return 0;
}

原文链接:http://www.cnblogs.com/kagula/p/13401674.html

 友情链接: NPS  问卷模板