线段树练习五 题解

线段树练习五

题目

一行$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

解题思路

主程序
建树
判断输入的是累加还是统计

累加
找到并相加

统计
统计区间里的和

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y;
char c;
struct hhx{int l,r,ans;
}t[500200];
void tree(int d,int l,int r)  //建树
{int mid=(l+r)/2;t[d].l=l;t[d].r=r;if (r!=l)tree(d*2,l,mid),tree(d*2+1,mid+1,r);
}
void add(int d,int l,int ans)  //累加
{ if (t[d].l==l&&t[d].r==l) {t[d].ans+=ans;  //找到相加return;}else if (l<=t[2*d].r)   //继续找add(2*d,l,ans);else add(d*2+1,l,ans);t[d].ans=t[d*2].ans+t[d*2+1].ans;
}
int tj(int d,int l,int r)  //统计
{ if (t[d].l==0||t[d].r==0)return 0;int mid=(t[d].l+t[d].r)/2;if (t[d].l==l&&t[d].r==r)return t[d].ans;if (r<=mid) return tj(d*2,l,r);else if (l>mid) return tj(d*2+1,l,r);else return tj(2*d,l,mid)+tj(d*2+1,mid+1,r);
}
int main()
{scanf("%d%d",&n,&m);tree(1,1,n);for (int i=1;i<=m;i++){cin>>c;scanf("%d%d",&x,&y);if (c=='M')add(1,x,y);else printf("%d\n",tj(1,x,y));}return 0;
}