线段树练习五

Description

一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N≤100000,提问和修改的总数可能达到100000条。

Input

20 //方格个数
6 //有几组操作
M 1 1 //表示修改,第一个表示格子位置,第二个数表示在原来的基础上加上的数,
M 2 2
M 3 4
M 3 -5
M 6 7
C 2 6 //表示统计 ,第一个数表示起始位置,第二个数表示结束位置

Output

8

解题思路

线段树练习题一

AC代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y,m,n,a[400010];
char c;
void insert(int dep,int l,int r)//修改
{
   
	int mid=(l+r)/2;
	if(l==r)
	{
   
		a[dep]+=y;
		return;
	} 
	if(x<=mid)insert(2*dep,l,mid);
	if(x>mid)insert(2*dep+1,mid+1,r);
	a[dep]+=y;
}
int sc(int dep,int l,int r,int x,int y)//查询
{
   
	if(r>m)return 0;
	if(l==x&&r==y)
		return a[dep];
	int mid=(l+r)/2;
	if(y<=mid) return sc(dep*2,l,mid,x,y);
	else if(x>mid) return sc(dep*2+1,mid+1,r,x,y);
	else return sc(dep*2,l,mid,x,mid)+sc(dep*2+1,mid+1,r,mid+1,y);
}
int main()
{
   
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
   
		cin>>c;
		scanf("%d%d",&x,&y);
		if(c=='M')insert(1,1,m);
		if(c=='C')printf("%d\n",sc(1,1,m,x,y));
	}
}

谢谢