c/c++语言开发共享线段树学习笔记

 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 }