树状数组

模板1 （P3374)

单点修改，区间查询

#include <iostream>  
using namespace std;

int n,m,t[500010];

void myadd(int pos,int x)//构建
{
	while(pos<=n)
	{
		t[pos]+=x;
		pos+=(pos&-pos);
	}
}

int mysum(int pos)//查询0到pos的区间和
{
	int s=0;
	while(pos)
	{
		s+=t[pos];
		pos-=(pos&-pos);
	}
	return s;
}

void lesson1()
{
	int type,a,b;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a;
		myadd(i,a);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>type>>a>>b;
		if(type==2) cout<<mysum(b)-mysum(a-1)<<endl;
		else myadd(a,b);
	}
}

int main()
{
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr); 
	lesson1();
	return 0;
}

模板2（P3368)

区间修改，单点查询,要利用到差分数组来构建

#include <iostream>  
using namespace std;

int t[500010],n,m;

void myadd(int pos,int x)
{
	while(pos<=n)
	{
		t[pos]+=x;
		pos+=pos&-pos;
	}
}

int mysum(int pos)
{
	int s=0;
	while(pos)
	{
		s+=t[pos];
		pos-=pos&-pos;
	}
	return s;
}

void lesson1()
{
	int type,x=0,y,a;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>y;
		myadd(i,y-x);
		x=y;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>type;
		if(type==2)
		{
			cin>>x;
			cout<<mysum(x)<<endl;
		}
		else 
		{
			cin>>x>>y>>a;
			myadd(x,a);
			myadd(y+1,-a);
		}
	}
}

int main()
{
	lesson1();
	return 0;
}