線段樹學習筆記

 1 #include<iostream>
 2 using namespace std;
 3 struct tree{
 4 　　int l,r,sum;
 5 }t[1000001];
 6 int a[1000001],n,p,x,y,m;
 7 inline void build(int root,int left,int right)
 8 {
 9 　　t[root].l=left;t[root].r=right;
10 　　if(left==right){t[root].sum=a[left];return;}
11 　　int child(root<<1),mid((left+right)>>1);
12 　　build(child,left,mid);build(child+1,mid+1,right);
13 　　t[root].sum=t[child].sum+t[child+1].sum;
14 }
15 inline int search(int root,int left,int right)
16 {
17 　　if((t[root].l>=left)&&(t[root].r<=right))
18 　　　　return t[root].sum;
19 　　if((t[root].r<left)||(t[root].l>right))
20 　　　　return 0;
21 　　int local_sum(0),child(root<<1);
22 　　if(t[child].r>=left)
23 　　　　local_sum+=search(child,left,right);
24 　　if(t[child+1].l<=right)
25 　　　　local_sum+=search(child+1,left,right);
26 　　return local_sum;
27 }
28 inline void add(int root,int goal,int plus)
29 {
30 　　if(t[root].l==t[root].r)
31 　　{
32 　　　　t[root].sum+=plus;
33 　　　　return;
34 　　}
35 　　int child(root<<1);
36 　　if(goal<=t[child].r)
37 　　　　add(child,goal,plus);
38 　　else
39 　　　　add(child+1,goal,plus);
40 　　t[root].sum=t[child].sum+t[child+1].sum;
41 }
42 int main()
43 {
44 　　cin>>n>>m;
45 　　for(int i=1;i<=n;i++)
46 　　　　cin>>a[i];
47 　　build(1,1,n);
48 　　for(int i=0;i<m;i++)
49 　　{
50 　　　　cin>>p>>x>>y;
51 　　　　if(p==1)
52 　　　　　　add(1,x,y);
53 　　　　else
54 　　　　cout<<search(1,x,y)<<endl;
55 　　}
56 　　return 0;
57 }