---

题目描述

给定一个初始值都为0的序列，动态地修改一些位置上的数字,加上一个数,减去一个数,然后动态地提出问题,问题的形式是求出一段数字的和。 规定： 　　Add i d 表示将序列第i个数加上d； 　　Sub i d 表示将序列中第i数减去d； 　　Ask i j 询问序列i到j的所有数的和；

---

输入格式

输入文件的第一行两个整数：n m，分别表示序列的长度和有m条指令；第2行到第m+1行，都是上面所示的指令格式，没有多余的空格；

---

输出格式

输出文件的每行一个整数，分别对指令序列中的ask做出的回答。

---

样例数据

样例输入

10 6 Add 2 3 Sub 3 1 Ask 3 7 Add 4 2 Ask 3 6 Sub 1 1

样例输出

-1 1

---

数据范围

动态加减的数d与序列中所有数据之和不会超过Longint范围 1<=n<=100000 1<=m<=200000

---

题目分析

线段树 点修改查询区间 或 树状数组 模板题

---

源代码

线段树

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=100000; struct Tree { //修改点 查询区间 int left,right,data; }; struct Segment_Tree { //执行加法操作 Tree tree[maxn*4]; int sum; void build(int index,int Left,int Right) { tree[index].left=Left; tree[index].right=Right; tree[index].data=0; if(Left==Right)return; int mid=(Left+Right)/2; build(2*index,Left,mid); build(2*index+1,mid+1,Right); } void increase(int index,int target,int delta) { //增加点的值 if(target<tree[index].left||target>tree[index].right)return; //不相交 if(target>=tree[index].left&&target<=tree[index].right)tree[index].data+=delta; //完全包含 if(tree[index].left==tree[index].right)return; //叶子节点 increase(index*2,target,delta); increase(index*2+1,target,delta); } void init() { //注意多次询问一定要调用 sum=0; } void Query(int index,int Left,int Right) { //查询区间值 if(Right<tree[index].left||Left>tree[index].right)return; //不相交 if(Left<=tree[index].left&&Right>=tree[index].right) { //完全包含 sum+=tree[index].data; return; } Query(index*2,Left,Right); Query(index*2+1,Left,Right); } }; Segment_Tree st; int n,m; int main() { ios::sync_with_stdio(false); cin>>n>>m; st.build(1,1,n); for(int i=1; i<=m; i++) { string order; cin>>order; if(order=="Add") { int target,delta; cin>>target>>delta; st.increase(1,target,delta); } else if(order=="Sub") { int target,delta; cin>>target>>delta; st.increase(1,target,-delta); } else { int Left,Right; cin>>Left>>Right; st.init(); st.Query(1,Left,Right); printf("%d\n",st.sum); } } return 0;

树状数组

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=500005; struct BIT { //树状数组 int n,c[maxn]; inline int Lowbit(int x) { //低位操作 return x&(-x); } void init(int n) { this->n=n; memset(c,0,sizeof(c)); } void Add(int x,int v) { for(int i=x; i<=n; i+=Lowbit(i))c[i]+=v; } int Sum(int x) { //求出1~x的区间和 int s=0; for(int i=x; i; i-=Lowbit(i))s+=c[i]; return s; } }; BIT Tree; int n,m; int main() { cin>>n>>m; Tree.init(n); for(int i=1; i<=m; i++) { string order; int a,b; cin>>order>>a>>b; if(order=="Add")Tree.Add(a,b); else if(order=="Sub")Tree.Add(a,-b); else printf("%d\n",Tree.Sum(b)-Tree.Sum(a-1)); } return 0; }

---