题目描述
给一个数列，会有多次询问，对于每一次询问，会有两种操作：
1：给定两个整数x, y, 然后在原数组的第x位置上加y；
2：给定两个整数l，r，然后输出数组从第l位加到第r位数字的和并换行
输入描述:
第一行有两个整数n, m（1 <= n, m <= 100000）代表数列的长度和询问的次数
第二行n个数字，对于第i个数字a[i]，(0<=a[i]<=100000)。
接下来m行，每一行有三个整数f, x, y。第一个整数f是1或者是2，代表操作类型，如果是1，接下来两个数x,y代表第x的位置上加y，如果是2，则求x到y的和，保证数据合法。
输出描述:
输出每次求和的结果并换行
示例
输入
10 2
1 2 3 4 5 6 7 8 9 10
1 1 9
2 1 10
输出
64
解析
线段树单点更新,区间查询,模板题,洒洒水啦~~
#include<iostream> #include<algorithm> #define int long long #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e5+10; int a[N]; int sum[N<<2]; void build(int root,int l,int r) { if(l == r) { sum[root] = a[l]; return ; } int rt = root<<1; int mid = l+r >>1; build(rt,l,mid); build(rt+1,mid+1,r); sum[root] = sum[rt] + sum[rt+1]; } void update(int root,int l,int r,int pos, int val) { if(l == r) { sum[root]+=val; return ; } int rt = root<<1; int mid = l+r >>1; if(pos<=mid) update(rt,l,mid,pos,val); else update(rt+1,mid+1,r,pos,val); sum[root] = sum[rt] + sum[rt+1]; } int find(int root,int l,int r,int ql,int qr) { //如果本区间完全包含在[ql,qr]里面,直接返回 if(ql<=l && r<=qr) return sum[root]; int rt = root<<1; int mid = l+r >>1; int ans = 0; if(ql<=mid) ans+=find(rt,l,mid,ql,qr); if(qr>mid) ans+=find(rt+1,mid+1,r,ql,qr); return ans; } signed main() { int n,m,f,x,y; cin>>n>>m; rep(i,1,n) cin>>a[i]; build(1,1,n); rep(i,1,m) { cin>>f>>x>>y; if(f == 1) { update(1,1,n,x,y); }else { cout<<find(1,1,n,x,y)<<endl; } // rep(i,1,n<<1) cout<<"sum["<<i<<"]:"<<sum[i]<<endl; } return 0; }
