欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

线段树学习笔记

程序员文章站 2022-05-18 21:12:58
1 #include 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 }