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 …

 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 }

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/600845.html

(0)
上一篇 2021年5月9日
下一篇 2021年5月9日

精彩推荐