B.Big Water Problem
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
给一个数列，会有多次询问，对于每一次询问，会有两种操作：
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的和，保证数据合法。
输出描述:
输出每次求和的结果并换行
示例1
输入
10 2 1 2 3 4 5 6 7 8 9 10 1 1 9 2 1 10
输出
64
这个题就是线段树的区间查询求和和单点更新。
传送3篇写的可以的线段树的博客，看完就会了(大一学的，没怎么用，就忘了，还要重新看。。。)
代码:
1 //B-线段树-区间查询求和和单点更新
2 #include<iostream>
3 #include<cstring>
4 #include<cstdio>
5 #include<cstdlib>
6 #include<algorithm>
7 using namespace std;
8 typedef long long ll;
9 #define ls l,m,rt<<1
10 #define rs m+1,r,rt<<1|1
11 #define root 1,n,1
12 const int maxn=1e5+10;
13 ll Sum[maxn<<2],Add[maxn<<2];//Sum为求和，Add为懒惰标记
14 ll A[maxn],n;//存原数组数据下标
15
16 //PushUp函数更新节点信息，这里是求和
17 void PushUp(int rt){
18 Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];
19 }
20
21 //下推标记的函数
22 void PushDown(int rt,int m){
23 if(Add[rt]){//下推标记
24 Add[rt<<1]+=Add[rt];
25 Add[rt<<1|1]+=Add[rt];
26 Sum[rt<<1]+=Add[rt]*(m-(m>>1));
27 Sum[rt<<1|1]+=Add[rt]*(m>>1);
28 Add[rt]=0;//清除本节点标记
29 }
30 }
31
32 //建树
33 void Build(int l,int r,int rt){//rt表示当前节点编号
34 Add[rt]=0;
35 if(l==r){
36 Sum[rt]=A[l];return;
37 }
38 int m=(l+r)>>1;
39 Build(ls);
40 Build(rs);
41 PushUp(rt);
42 }
43
44 //区间修改A[L,R]+=C
45 //void Update(int L,int R,int C,int l,int r,int rt){
46 // if(L<=l&&r<=R){
47 // Sum[rt]+=(ll)C*(r-l+1);
48 // Add[rt]+=C;
49 // return ;
50 // }
51 // PushDown(rt,r-l+1);//下推标记
52 // int m=(l+r)>>1;
53 // if(L<=m)Update(L,R,C,ls);
54 // if(R>m)Update(L,R,C,rs);
55 // PushUp(rt);//更新本节点
56 //}
57
58 //点修改A[L]+=C
59 void Update(int L,int C,int l,int r,int rt){
60 if(l==r){
61 Sum[rt]+=C;
62 return ;
63 }
64 int m=(l+r)>>1;
65 if(L<=m)Update(L,C,ls);
66 else Update(L,C,rs);
67 PushUp(rt);
68 }
69
70 //区间查询A[L,R]的和
71 int Query(int L,int R,int l,int r,int rt){
72 if(L<=l&&r<=R){
73 return Sum[rt];
74 }
75 PushDown(rt,r-l+1);//下推标记，否则Sum可能不正确
76 int m=(l+r)>>1;
77 ll ANS=0;//累计答案
78 if(L<=m)ANS+=Query(L,R,ls);
79 if(R>m)ANS+=Query(L,R,rs);
80 return ANS;
81 }
82
83 int main(){
84 int n,m;
85 scanf("%d%d",&n,&m);
86 for(int i=1;i<=n;i++)
87 scanf("%lld",&A[i]);
88 Build(1,n,1);//建树
89 while(m--){
90 int x;
91 scanf("%d",&x);
92 if(x==2){
93 int a,b;
94 scanf("%d%d",&a,&b);
95 ll ANS=Query(a,b,root);//区间查询
96 printf("%lld
",ANS);
97 }
98 else{
99 int a,C;
100 scanf("%d%d",&a,&C);
101 Update(a,C,root);//区间修改
102 }
103 }
104 return 0;
105 }