Acwing 1264. 动态求连续区间和(树状数组模板)

Acwing 1264. 动态求连续区间和(树状数组模板)

树状数组的基本操作:修改某个数(维护区间),求区间和

①修改(给第x个数加c)

void add(int x,int c)
{
	w[x]+=c;
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}

②求区间和 (1~x的区间和)

若求[a,b]区间和,则为sum(b)-sum(a-1)

int sum(int x)
{
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i))
		res+=tr[i];
	return res;
}

 整体代码:(注意使用add(i,w[i])初始化树状数组)

#include<iostream>
using namespace std;

const int N=1e5+5;
int w[N];
int tr[N];
int n,m;
int lowbit(int x)
{
	return x&-x;
} 
int sum(int x)
{
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i))
		res+=tr[i];
	return res;
}
void add(int x,int c)
{
	w[x]+=c;
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=c;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) 
		cin>>w[i],add(i,w[i]);
	while(m--)
	{
		int k,a,b;cin>>k>>a>>b;
		if(!k)	cout<<sum(b)-sum(a-1)<<endl;
		else add(a,b);
	}
}

上一篇:动态规划之01背包和完全背包问题(力扣C++题解)


下一篇:2421 Problem C 最快合并链表(线性表)