线段树模板

1、求区间和

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 const int maxn=50000+5;
 5 int a[maxn];
 6 struct Node
 7 {
 8     int l,r,sum;
 9 } node[maxn<<2];
10 
11 //参数含义：节点区间，节点编号
12 void InitTree(int l,int r,int k)
13 {
14     node[k].r=r;//节点k的右子树
15     node[k].l=l;
16     node[k].sum=0;//权值
17     if(l==r)//到达叶子节点
18     {
19         node[k].sum=a[r];
20         return;
21     }
22     int mid=(l+r)>>1;
23     InitTree(l,mid,k<<1);//递归建左子树
24     InitTree(mid+1,r,k<<1|1);//递归建右子树
25 
26     node[k].sum=node[k<<1].sum+node[k<<1|1].sum;
27     //父节点的值为两子节点值的和
28     //此为线段树的核心所在，求最值修改这一句即可
29 }
30 void UpdateTree(int l,int r,int k,int sum)
31 {
32     if(node[k].l==l&&node[k].r==r)
33     {
34         node[k].sum+=sum;
35         return;
36     }
37     int mid=(node[k].l+node[k].r)>>1;
38     if(l>mid)
39         UpdateTree(l,r,k<<1|1,sum);//更新下一层的右子树
40     else
41         UpdateTree(l,r,k<<1,sum);
42 
43     node[k].sum=node[k<<1].sum+node[k<<1|1].sum;
44     //注意：每次更新后也要更新父节点的值
45 }
46 //查询l到r的k
47 int SearchTree(int l,int r,int k)
48 {
49     if(node[k].l==l&&node[k].r==r)
50     {
51         return node[k].sum;
52     }
53     int mid=(node[k].l+node[k].r)>>1;
54     if(l>mid)
55     {
56         return SearchTree(l,r,k<<1|1);//查询右子树
57     }
58     else if(r<=mid)
59     {
60         return SearchTree(l,r,k<<1);
61     }
62     else
63     {
64         //查询区间横跨左右子树，两棵子树一起查询
65         return SearchTree(mid+1,r,k<<1|1)+SearchTree(l,mid,k<<1);
66     }
67 }
68 int main()
69 {
70     int T,kase=0;
71     cin>>T;
72     while(T--)
73     {
74         printf("Case %d:
",++kase);
75         int n,x,y;
76         scanf("%d",&n);
77         for(int i=1;i<=n;i++)
78         {
79             scanf("%d",&a[i]);
80         }
81         InitTree(1,n,1);
82         char ch[10];
83         while(scanf("%s",ch))
84         {
85             if(ch[0]=='E')
86                 break;
87             scanf("%d%d",&x,&y);
88             if(ch[0]=='A')
89                 UpdateTree(x,x,1,y);
90             else if(ch[0]=='S')
91                 UpdateTree(x,x,1,-y);
92             else if(ch[0]=='Q')
93                 cout<<SearchTree(x,y,1)<<endl;
94         }
95     }
96     return 0;
97 }

区间和

2、求区间最大值

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 const int maxn=200000+5;
 5 int a[maxn];
 6 struct Node
 7 {
 8     int l,r,sum;
 9 } node[maxn<<2];
10 
11 //参数含义：节点区间，节点编号
12 void InitTree(int l,int r,int k)
13 {
14     node[k].r=r;//节点k的右子树
15     node[k].l=l;
16     node[k].sum=0;//权值
17     if(l==r)//到达叶子节点
18     {
19         node[k].sum=a[r];
20         return;
21     }
22     int mid=(l+r)>>1;
23     InitTree(l,mid,k<<1);//递归建左子树
24     InitTree(mid+1,r,k<<1|1);//递归建右子树
25 
26     node[k].sum=max(node[k<<1].sum,node[k<<1|1].sum);
27     //父节点的值为两子节点值的和
28     ///此为线段树的核心所在，求最值修改这一句即可
29 }
30 void UpdateTree(int l,int r,int k,int sum)
31 {
32     if(node[k].l==l&&node[k].r==r)
33     {
34         node[k].sum=sum;
35         return;
36     }
37     int mid=(node[k].l+node[k].r)>>1;
38     if(l>mid)
39         UpdateTree(l,r,k<<1|1,sum);//更新下一层的右子树
40     else
41         UpdateTree(l,r,k<<1,sum);
42 
43     node[k].sum=max(node[k<<1].sum,node[k<<1|1].sum);
44     //注意：每次更新后也要更新父节点的值
45 }
46 //查询l到r的k
47 int SearchTree(int l,int r,int k)
48 {
49     if(node[k].l==l&&node[k].r==r)
50     {
51         return node[k].sum;
52     }
53     int mid=(node[k].l+node[k].r)>>1;
54     if(l>mid)
55     {
56         return SearchTree(l,r,k<<1|1);//查询右子树
57     }
58     else if(r<=mid)
59     {
60         return SearchTree(l,r,k<<1);
61     }
62     else
63     {
64         //查询区间横跨左右子树，两棵子树一起查询
65         return max(SearchTree(mid+1,r,k<<1|1),SearchTree(l,mid,k<<1));
66     }
67 }
68 int main()
69 {
70     int n,m;
71     while(scanf("%d%d",&n,&m)!=EOF)
72     {
73         int x,y;
74         for(int i=1;i<=n;i++)
75         {
76             scanf("%d",&a[i]);
77         }
78         InitTree(1,n,1);
79         char ch;
80         while(m--)
81         {
82             getchar();
83             scanf("%c",&ch);
84             scanf("%d%d",&x,&y);
85             if(ch=='U')
86                 UpdateTree(x,x,1,y);
87             else if(ch=='Q')
88                 printf("%d
",SearchTree(x,y,1));
89         }
90     }
91     return 0;
92 }

求最大值

3、更新版本（源自网络）（上面两个为更新结点，这个是更新区间）

  1 #include <string.h>
  2 #include <algorithm>
  3 #include <stdio.h>
  4 #include <math.h>
  5 #include <queue>
  6 #define MAXN 100010
  7 #define inf 0x3f3f3f3f
  8 
  9 using namespace std;
 10 
 11 struct node{
 12     long long l,r;//区间[l,r]
 13     long long add;//区间的延时标记
 14     long long sum;//区间和
 15  //   long long mx; //区间最大值
 16  //   long long mn; //区间最小值
 17 }tree[MAXN<<2];//一定要开到4倍多的空间
 18 
 19 void pushup(long long index){
 20     tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;
 21 //    tree[index].mx = max(tree[index<<1].mx,tree[index<<1|1].mx);
 22  //   tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
 23 }
 24 void pushdown(long long index){
 25     //说明该区间之前更新过
 26     //要想更新该区间下面的子区间，就要把上次更新该区间的值向下更新
 27     if(tree[index].add){
 28         //替换原来的值
 29         /*
 30         tree[index<<1].sum = (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;
 31         tree[index<<1|1].sum = (tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;
 32         tree[index<<1].mx = tree[index].add;
 33         tree[index<<1|1].mx = tree[index].add;
 34         tree[index<<1].mn = tree[index].add;
 35         tree[index<<1|1].mn = tree[index].add;
 36         tree[index<<1].add = tree[index].add;
 37         tree[index<<1|1].add = tree[index].add;
 38         tree[index].add = 0;*/
 39         //在原来的值的基础上加上val
 40 
 41         tree[index<<1].sum += (tree[index<<1].r-tree[index<<1].l+1)*tree[index].add;
 42         tree[index<<1|1].sum +=(tree[index<<1|1].r-tree[index<<1|1].l+1)*tree[index].add;
 43   //      tree[index<<1].mx += tree[index].add;
 44    //     tree[index<<1|1].mx += tree[index].add;
 45     //    tree[index<<1].mn += tree[index].add;
 46      //   tree[index<<1|1].mn += tree[index].add;
 47         tree[index<<1].add += tree[index].add;
 48         tree[index<<1|1].add += tree[index].add;
 49         tree[index].add = 0;
 50 
 51     }
 52 }
 53 void build(long long l,long long r,long long index){
 54     tree[index].l = l;
 55     tree[index].r = r;
 56     tree[index].add = 0;//刚开始一定要清0
 57     if(l == r){
 58         scanf("%d",&tree[index].sum);
 59     //    tree[index].mn = tree[index].mx = tree[index].sum;
 60         return ;
 61     }
 62     long long mid = (l+r)>>1;
 63     build(l,mid,index<<1);
 64     build(mid+1,r,index<<1|1);
 65     pushup(index);
 66 }
 67 void updata(long long l,long long r,long long index,long long val){
 68     if(l <= tree[index].l && r >= tree[index].r){
 69         /*把原来的值替换成val,因为该区间有tree[index].r-tree[index].l+1
 70         个数，所以区间和 以及 最值为：
 71         */
 72         /*tree[index].sum = (tree[index].r-tree[index].l+1)*val;
 73         tree[index].mn = val;
 74         tree[index].mx = val;
 75         tree[index].add = val;//延时标记*/
 76         //在原来的值的基础上加上val,因为该区间有tree[index].r-tree[index].l+1
 77         //个数，所以区间和 以及 最值为：
 78         tree[index].sum += (tree[index].r-tree[index].l+1)*val;
 79  //       tree[index].mn += val;
 80   //      tree[index].mx += val;
 81         tree[index].add += val;//延时标记
 82 
 83         return ;
 84     }
 85     pushdown(index);
 86     long long mid = (tree[index].l+tree[index].r)>>1;
 87     if(l <= mid){
 88         updata(l,r,index<<1,val);
 89     }
 90     if(r > mid){
 91         updata(l,r,index<<1|1,val);
 92     }
 93     pushup(index);
 94 }
 95 long long query(long long l,long long r,long long index){
 96     if(l <= tree[index].l && r >= tree[index].r){
 97         return tree[index].sum;
 98         //return tree[index].mx;
 99         //return tree[index].mn;
100     }
101     pushdown(index);
102     long long mid = (tree[index].l+tree[index].r)>>1;
103     long long ans = 0;
104   //  long long Max = 0;
105   //  long long Min = inf;
106     if(l <= mid){
107         ans += query(l,r,index<<1);
108    //     Max = max(query(l,r,index<<1),Max);
109     //    Min = min(query(l,r,index<<1),Min);
110     }
111     if(r > mid){
112         ans += query(l,r,index<<1|1);
113       //  Max = max(query(l,r,index<<1|1),Max);
114       //  Min = min(query(l,r,index<<1|1),Min);
115     }
116     return ans;
117    // return Max;
118     //return Min;
119 }
120 int main()
121 {
122     long long n,m,x,y,z;
123     char q;
124     scanf("%lld%lld",&n,&m);
125         build(1,n,1);
126         getchar();
127         while(m--){
128             scanf("%c",&q);
129             if(q == 'Q'){
130                 scanf("%lld%lld",&x,&y);
131                printf("%lld
",query(x,y,1));
132             }
133             else{
134                 scanf("%lld%lld%lld",&x,&y,&z);
135                 updata(x,y,1,z);
136                /* for(int i = 1; i <= n; ++i){
137                     printf("a[%d] = %d
",i,query(i,i,1));
138                 }*/
139             }
140             getchar();
141         }
142     return 0;
143 }

区间更新SUMMAXMIN

まだまだだね