线段树模板

知识点参考：http://www.cnblogs.com/TheRoadToTheGold/p/6254255.html

语法参考：https://blog.csdn.net/dimensionoffive/article/details/70054356

https://www.cnblogs.com/fnlingnzb-learner/p/6423917.html

题目：https://blog.csdn.net/yrhsilence/article/details/5793699

1.区间和

  1 #include<cstdio>
  2 using namespace std;
  3 int n,p,m,ans;//n个节点，m中操作，ans为操作时的中间变量
  4 struct node
  5 {
  6     int l,r,w,f;//l区间左端点，l区间右端点，w区间和，f懒惰标记
  7 }tree[400001];
  8 inline void build(int k,int ll,int rr)//建树,k节点序号，ll区间左端点，rr区间右端点
  9 {
 10     tree[k].l=ll,tree[k].r=rr;
 11     if(tree[k].l==tree[k].r)
 12     {
 13         scanf("%d",&tree[k].w);
 14         return;
 15     }
 16     int m=(ll+rr)/2;
 17     build(k*2,ll,m);
 18     build(k*2+1,m+1,rr);
 19     tree[k].w=tree[k*2].w+tree[k*2+1].w;
 20 }
 21 inline void down(int k)//标记下传，k节点序号
 22 {
 23     tree[k*2].f+=tree[k].f;
 24     tree[k*2+1].f+=tree[k].f;
 25     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
 26     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
 27     tree[k].f=0;
 28 }
 29 inline void ask_point(int x,int k)//单点查询，x要查询点
 30 {
 31     if(tree[k].l==tree[k].r)
 32     {
 33         ans=tree[k].w;
 34         return ;
 35     }
 36     if(tree[k].f) down(k);
 37     int m=(tree[k].l+tree[k].r)/2;
 38     if(x<=m) ask_point(x,k*2);
 39     else ask_point(x,k*2+1);
 40 }
 41 inline void change_point(int x,int y,int k)//单点修改,x要修改点,y要添加值
 42 {
 43     if(tree[k].l==tree[k].r)
 44     {
 45         tree[k].w+=y;
 46         return;
 47     }
 48     if(tree[k].f) down(k);
 49     int m=(tree[k].l+tree[k].r)/2;
 50     if(x<=m) change_point(x,y,k*2);
 51     else change_point(x,y,k*2+1);
 52     tree[k].w=tree[k*2].w+tree[k*2+1].w;
 53 }
 54 inline void ask_interval(int x,int y,int k)//区间查询，x查询区间左端，y查询区间右端
 55 {
 56     if(tree[k].l>=x&&tree[k].r<=y)
 57     {
 58         ans+=tree[k].w;
 59         return;
 60     }
 61     if(tree[k].f) down(k);
 62     int m=(tree[k].l+tree[k].r)/2;
 63     if(x<=m) ask_interval(x,y,k*2);
 64     if(y>m) ask_interval(x,y,k*2+1);
 65 }
 66 inline void change_interval(int x,int y,int num,int k)//区间修改，x区间左端，y区间右端，num要添加值
 67 {
 68     if(tree[k].l>=x&&tree[k].r<=y)
 69     {
 70         tree[k].w+=(tree[k].r-tree[k].l+1)*num;
 71         tree[k].f+=num;
 72         return;
 73     }
 74     if(tree[k].f) down(k);
 75     int m=(tree[k].l+tree[k].r)/2;
 76     if(x<=m) change_interval(x,y,num,k*2);
 77     if(y>m) change_interval(x,y,num,k*2+1);
 78     tree[k].w=tree[k*2].w+tree[k*2+1].w;
 79 }
 80 int main()
 81 {
 82     //freopen("in.txt","r",stdin);
 83     scanf("%d",&n);//n个节点
 84     build(1,1,n);//建树
 85     scanf("%d",&m);//m种操作，在线段树题中不要用cin,cout!
 86     for(int i=1;i<=m;i++)
 87     {
 88         scanf("%d",&p);
 89         ans=0;//ans为全局变量
 90         int x,y,a,b;
 91         if(p==1)
 92         {
 93             scanf("%d",&x);
 94             ask_point(x,1);//单点查询,输出第x个数
 95             printf("%d
",ans);
 96         }
 97         else if(p==2)
 98         {
 99             scanf("%d%d",&x,&y);
100             change_point(x,y,1);//单点修改
101         }
102         else if(p==3)
103         {
104             scanf("%d%d",&a,&b);//区间查询
105             ask_interval(a,b,1);
106             printf("%d
",ans);
107         }
108         else
109         {
110              scanf("%d%d%d",&a,&b,&y);//区间修改
111              change_interval(a,b,y,1);
112         }
113     }
114 }
115 /*输入
116 10
117 1 2 3 4 5 6 7 8 9 10
118 10
119 1 1
120 1 10
121 2 1 11
122 2 10 11
123 3 1 10
124 3 10 10
125 4 1 10 2
126 4 1 1 2
127 1 6
128 3 5 5
129 */
130 
131 /*输出
132 1
133 10
134 77
135 21
136 8
137 7
138 */

2.区间最大值

  1 #include <iostream>
  2 #include <cstdio>
  3 using namespace std;
  4 
  5 #define MAX_N 200000
  6 
  7 int big;//存答案
  8 typedef struct node
  9 {
 10     int left;
 11     int right;
 12     int data;//存数
 13     int maxx;//存最大值
 14 }node;
 15 
 16 node stu[MAX_N*4];
 17 //int num[MAX_N+1];
 18 
 19 int Max(int a,int b)
 20 {
 21     return a>b?a:b;
 22 }
 23 
 24 void CreateTree(int ii,int a,int b)//ii节点，a左区间，b右区间
 25 {
 26     stu[ii].left = a;
 27     stu[ii].right = b;
 28     stu[ii].maxx = 0;
 29     stu[ii].data = 0;
 30     if(a == b)
 31     {
 32         return;
 33     }
 34     else
 35     {
 36         int mid = (a+b)>>1;
 37         CreateTree(ii*2,a,mid);
 38         CreateTree(ii*2+1,mid+1,b);
 39     }
 40 }
 41 
 42 void updata(int ii,int a,int b)//单点更新，ii节点序号，第a个位置，更新为b值
 43 {
 44     if(stu[ii].left == a && stu[ii].right == a)
 45     {
 46         stu[ii].data = b;
 47         stu[ii].maxx = b;
 48     }
 49     else
 50     {
 51         int mid = (stu[ii].left+stu[ii].right)>>1;
 52         if(a <= mid)
 53         {
 54             updata(ii*2,a,b);
 55         }
 56         else
 57         {
 58             updata(ii*2+1,a,b);
 59         }
 60         if(b > stu[ii].maxx)//回溯更新
 61             stu[ii].maxx = b;
 62     }
 63 }
 64 
 65 void find(int ii,int a,int b)//区间查询，ii节点序号，a左端点，b右端点
 66 {
 67     if(stu[ii].left == a && stu[ii].right == b)
 68     {
 69         //printf("%d/n",stu[ii].maxx);
 70         if(stu[ii].maxx > big)
 71             big = stu[ii].maxx;
 72     }
 73     else
 74     {
 75         int mid = (stu[ii].left + stu[ii].right)>>1;
 76         if(b <= mid)
 77         {
 78             find(ii*2,a,b);
 79         }
 80         else if(a > mid)
 81         {
 82             find(ii*2+1,a,b);
 83         }
 84         else
 85         {
 86             find(ii*2,a,mid);
 87             find(ii*2+1,mid+1,b);
 88         }
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     int n,m,num;//n节点数，m个操作,num为临时量
 95     int i;
 96 
 97 //    freopen("in.txt","r",stdin);
 98     while(scanf("%d%d",&n,&m)!=EOF)
 99     {
100         CreateTree(1,1,n);
101         for(i=1;i<=n;i++)
102         {
103             scanf("%d",&num);
104             updata(1,i,num);
105         }
106         char c;
107         int x1,x2;
108         while(m--)
109         {
110             getchar();
111             scanf("%c",&c);
112             scanf("%d%d",&x1,&x2);
113             if(c == 'Q')
114             {
115                 big = 0x80000000;//是一个很小的负数
116                 find(1,x1,x2);
117                 printf("%d
",big);
118             }
119             else
120             {
121                 updata(1,x1,x2);
122             }
123         }
124     }
125     return 0;
126 }

3.成段更新，总区间求和

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 #define MAX_N 100000
 5 
 6 struct node
 7 {
 8     int left;
 9     int right;
10     int data;//懒惰标记
11     int sum;//区间和
12 };
13 node hook[4*MAX_N];
14 
15 void CreateTree(int ii,int a,int b)
16 {
17     hook[ii].left = a;
18     hook[ii].right = b;
19     if(a == b)
20     {
21 //        hook[ii].data = 1;//此句似乎不影响结果
22         hook[ii].sum = 1;
23     }
24     else
25     {
26         int mid = (a+b)>>1;
27         CreateTree(ii*2,a,mid);
28         CreateTree(ii*2+1,mid+1,b);
29         hook[ii].data = 0;
30         hook[ii].sum = (hook[ii*2].sum + hook[ii*2+1].sum);
31     }
32 }
33 
34 void updata(int ii,int a,int b,int c)//区间修改，ii节点序号，a左端点，b右端点，c更改值
35 {
36     if(hook[ii].left == a && hook[ii].right == b)
37     {
38         hook[ii].data = c;
39         hook[ii].sum = (b-a+1)*c;
40     }
41     else
42     {
43         if(hook[ii].data > 0)
44         {
45             hook[ii*2].data = hook[ii].data;
46             hook[ii*2].sum = (hook[ii*2].right - hook[ii*2].left+1)*hook[ii*2].data;
47             hook[ii*2+1].data = hook[ii].data;
48             hook[ii*2+1].sum = (hook[ii*2+1].right - hook[ii*2+1].left+1)*hook[ii*2+1].data;
49         }
50         hook[ii].data = 0; //写的时候这个丢掉了。一直错
51         int mid = (hook[ii].left + hook[ii].right)>>1;
52         if(b <= mid)
53         {
54             updata(ii*2,a,b,c);
55         }
56         else if(a > mid)
57         {
58             updata(ii*2+1,a,b,c);
59         }
60         else
61         {
62             updata(ii*2,a,mid,c);
63             updata(ii*2+1,mid+1,b,c);
64         }
65         hook[ii].sum = hook[ii*2].sum + hook[ii*2+1].sum;
66     }
67 }
68 
69 
70 int main()
71 {
72     int t,n,m,x1,x2,x3;
73     int i;
74 //    freopen("in.txt","r",stdin);
75     scanf("%d",&t);
76     for(i=1;i<=t;i++)
77     {
78         scanf("%d",&n);
79         CreateTree(1,1,n);
80         scanf("%d",&m);
81         while(m--)
82         {
83             scanf("%d%d%d",&x1,&x2,&x3);
84             updata(1,x1,x2,x3);
85         }
86         printf("Case %d: The total value of the hook is %d.
",i,hook[1].sum);
87     }
88     return 0;
89 }

4.更新节点,区间求和(实现nlog(n)的逆序数方法

 1 #include <stdio.h>
 2 #include <algorithm>
 3 
 4 using namespace std;
 5 
 6 int a[5005];
 7 struct Node{
 8     int l,r,num;//num该区间已出现数的个数
 9 }tree[50000];
10 
11 void Build(int n,int x,int y){
12     tree[n].l = x;
13     tree[n].r = y;
14     tree[n].num = 0;
15     if(x == y){
16         return;
17     }
18     int mid = (x + y) / 2;
19     Build(2*n,x,mid);
20     Build(2*n+1,mid+1,y);
21 }
22 
23 void Modify(int n,int x){//在输入的相应叶节点加1
24     int l = tree[n].l;
25     int r = tree[n].r;
26     int mid = (l + r) / 2;
27     if(x == l && x == r){
28         tree[n].num = 1;
29         return;
30     }
31     if(x <= mid)    Modify(2*n,x);
32     else            Modify(2*n+1,x);
33     tree[n].num = tree[2*n].num + tree[2*n+1].num;
34 }
35 
36 int Query(int n,int x,int y){//求大于该数且已经出现的数个数，n节点序号，x左端点，y右端点
37     int l = tree[n].l;
38     int r = tree[n].r;
39     int mid = (l + r) / 2;
40     int ans = 0;
41     if(x == l && y == r)
42         return tree[n].num;
43     if(x <= mid)   ans += Query(2*n,x,min(mid,y));
44     if(y > mid)    ans += Query(2*n+1,max(mid+1,x),y);
45     return ans;
46 }
47 int main(){
48     int n,sum,ans;
49     int i,j;
50 
51     while(scanf("%d",&n) != EOF){
52         sum = 0;
53         Build(1,0,n-1);//区间端点取0~n-1即可
54         for(i = 1;i <= n;i++){
55             scanf("%d",&a[i]);
56             Modify(1,a[i]);
57             sum += Query(1,a[i]+1,n-1);
58         }
59         ans = sum;
60         for(i = 1;i < n;i++){
61             sum = sum + (n - 1 - a[i]) - a[i];//根据递推式加上接下来依次循环的序列的逆序数
62             if(sum < ans)
63                 ans = sum;//要最小的
64         }
65         printf("%d
",ans);
66     }
67 }

6。线段树区间染色问题

  1 /*
  2    功能Function Description:     POJ 2777 线段树
  3    开发环境Environment:          DEV C++ 4.9.9.1
  4    技术特点Technique:
  5    版本Version:
  6    作者Author:                   可笑痴狂
  7    日期Date:                      20120808
  8    备注Notes:
  9 题意：
 10     给定一个长度为N(N <= 100000)的数列Si，紧接着Q(Q <= 100000)条操作，操作
 11 形式有两种：
 12 1. "C A B C" 将A到B的数都染成C这种颜色。
 13 2. "P A B" 输出A和B之间不同颜色的数目。
 14 
 15 
 16 解法：-------转
 17 线段树（染色问题）
 18 
 19 思路：
 20     一看到数据量就可以首先确定是线段树了，经典的区间染色问题，涉及到区间的
 21 更新和询问，和pku 3468 类似，巧妙运用lazy思想。就是每次更新区间段的时候延迟
 22 更新，只是在完全覆盖的区间打上一个lazy标记。这题的询问是求区间段中不同颜色的
 23 数量，因为颜色数不多只有30种，可以巧妙运用二进制位运算，用一个int就可以表示
 24 当前区间段的颜色情况。比如1001表示有两种颜色，如果左子树的当前颜色情况是101
 25 ，而右子树的颜色情况是011，那么父亲的颜色情况就是两者的位或，这样就可以避免
 26 掉重复的情况。
 27     再来谈谈lazy思想。做了这么多的线段树，应该总结一下，lazy是一个很经典的思
 28 想。所谓lazy，就是懒惰，每次不想做太多，只要插入的区间完全覆盖了当前结点所管
 29 理的区间就不再往下做了，在当前结点上打上一个lazy标记，然后直接返回。下次如果
 30 遇到当前结点有lazy标记的话，直接传递给两个儿子，自己的标记清空。这样做肯定是
 31 正确的。我们以染色为例，可以这样想，如果当前结点和它的子孙都有lazy标记的话，
 32 必定是子孙的先标记，因为如果是自己先标记，那么在访问子孙的时候，必定会将自己
 33 的标记下传给儿子，而自己的标记必定会清空，那么lazy标记也就不存在了。所以可以
 34 肯定，当前的lazy标记必定覆盖了子孙的，所以直接下传即可，不需要做任何判断。当
 35 然，这是染色问题，是直接赋值的，如果像pku 3468那样，每次是区间加和，则传递标
 36 记的时候不能简单的赋值，必须累加，这是显而易见的。
 37 */
 38 
 39 
 40 //这是仿照别人写的AC代码
 41 #include<stdio.h>
 42 
 43 struct node
 44 {
 45     int lc,rc;
 46     int state;    //用二进制的每一位中的1的个数来标记颜色的个数，该数并不是颜色个数，而代表该区间的颜色集合
 47     int id;       //标记状态看是否被完全覆盖
 48 }tree[300010];
 49 
 50 
 51 void build(int s,int t,int T)
 52 {
 53     int mid;
 54     tree[T].lc=s;
 55     tree[T].rc=t;
 56     if(s==t)
 57         return ;
 58     mid=(s+t)>>1;
 59     build(s,mid,T<<1);
 60     build(mid+1,t,(T<<1)|1);   //位运算，等价于build(mid+1,t,(T<<1)+1);
 61 }
 62 
 63 void insert(int s,int t,int T,int value)       //从s到t涂上颜色value，从T节点开始查找
 64 {
 65     int mid;
 66     if(tree[T].lc==s&&tree[T].rc==t)    //说明涂色范围正好完全覆盖T所包含的区域，直接更新颜色信息，下边的节点不用管
 67     {
 68         tree[T].id=1;     //标记为完全覆盖
 69         tree[T].state=1<<(value-1);     //不同的颜色用2进制不同位上的1表示，如颜色1为最右位的1
 70         return ;
 71     }
 72     if(tree[T].id)      //说明T是完全覆盖的，更新T孩子节点的信息
 73     {
 74         tree[T].id=0;
 75         tree[T<<1].id=tree[(T<<1)|1].id=1;
 76         tree[T<<1].state=tree[(T<<1)|1].state=tree[T].state;//子区间颜色与父区间颜色相同
 77     }
 78     mid=(tree[T].lc+tree[T].rc)>>1;
 79     if(t<=mid)
 80         insert(s,t,T<<1,value);
 81     else if(s>mid)
 82         insert(s,t,(T<<1)|1,value);
 83     else
 84     {
 85         insert(s,mid,T<<1,value);
 86         insert(mid+1,t,(T<<1)|1,value);
 87     }
 88     tree[T].state=(tree[T<<1].state)|(tree[T<<1|1].state);// 等同于把颜色数相加，排除了相同颜色的重复计算
 89     if(tree[T<<1].id&&tree[(T<<1)|1].id&&tree[T<<1].state==tree[(T<<1)|1].state)//相当于父区间也全覆盖
 90         tree[T].id=1;
 91 }
 92 
 93 int qurry(int s,int t,int T)          //从T节点开始查询区间s到t颜色的个数
 94 {
 95     int mid;
 96     if(tree[T].lc==s&&tree[T].rc==t)
 97         return tree[T].state;
 98     if(tree[T].id)       //减枝----说明T是全覆盖的直接返回状态值即可
 99         return tree[T].state;
100     mid=(tree[T].lc+tree[T].rc)>>1;
101     if(t<=mid)
102         return qurry(s,t,T<<1);
103     else if(s>mid)
104         return qurry(s,t,(T<<1)|1);
105     else
106         return qurry(s,mid,T<<1)|qurry(mid+1,t,(T<<1)|1);
107 }
108 
109 int main()
110 {
111     int i,j,k,color,t,num,len,m;
112     char cmd[2];
113     while(scanf("%d%d%d",&len,&color,&m)!=EOF)
114     {
115         build(1,len,1);
116         tree[1].state=1;
117         tree[1].id=1;
118         while(m--)
119         {
120             scanf("%s",cmd);
121             if(cmd[0]=='C')
122             {
123                 scanf("%d%d%d",&i,&j,&k);
124                 if(i>j)
125                 {
126                     t=i;
127                     i=j;
128                     j=t;
129                 }
130                 insert(i,j,1,k);
131             }
132             else
133             {
134                 scanf("%d%d",&i,&j);
135                 if(i>j)
136                 {
137                     t=i;
138                     i=j;
139                     j=t;
140                 }
141                 k=qurry(i,j,1);
142                 num=0;
143                 for(i=0;i<color;++i)
144                     if(k&(1<<i))
145                         ++num;
146                 printf("%d
",num);
147             }
148         }
149     }
150     return 0;
151 }

区间和，区间最大值（无懒惰标记）融合模板：

算法训练操作格子
时间限制：1.0s 内存限制：256.0MB

问题描述
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。

模板参考：https://blog.csdn.net/acmman/article/details/18631017

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=1e5+5;//运行超时的话要注意此处空间是否够大！
  4 struct node
  5 {
  6     int l,r,sum,ma;
  7 }no[N*4];
  8 void build(int id,int l,int r)//建树
  9 {
 10     no[id].l=l;
 11     no[id].r=r;
 12     no[id].sum=no[id].ma=0;
 13     if (l==r)
 14         return;
 15     int mid=(l+r)/2;
 16     build(id*2,l,mid);
 17     build(id*2+1,mid+1,r);
 18 }
 19 void change(int id,int v,int val)//节点赋值
 20 {
 21     if (no[id].l==v&&no[id].r==v)//判断条件写错会导致死循环！
 22     {
 23         no[id].sum=no[id].ma=val;
 24         return;//不要漏掉return！！
 25     }
 26     int mid=(no[id].l+no[id].r)/2;
 27     if (v<=mid)
 28         change(id*2,v,val);
 29     else
 30         change(id*2+1,v,val);
 31     no[id].sum=no[id*2].sum+no[id*2+1].sum;
 32     no[id].ma=max(no[id*2].ma,no[id*2+1].ma);
 33 }
 34 int qsum(int id,int l,int r)//区间和
 35 {
 36     if (no[id].l==l&&no[id].r==r)
 37     {
 38         return no[id].sum;
 39     }
 40     int mid=(no[id].l+no[id].r)/2;
 41     if (r<=mid)//注意r，和l不要弄反！
 42         return qsum(id*2,l,r);
 43     else if (l>mid)
 44         return qsum(id*2+1,l,r);
 45     else
 46         return qsum(id*2,l,mid)+qsum(id*2+1,mid+1,r);
 47 }
 48 int qmax(int id,int l,int r)//区间最大值
 49 {
 50     if (l==no[id].l&&no[id].r==r)
 51     {
 52         return no[id].ma;
 53     }
 54     int mid=(no[id].l+no[id].r)/2;
 55     if (r<=mid)
 56         return qmax(id*2,l,r);
 57     else if (l>mid)
 58         return qmax(id*2+1,l,r);
 59     else
 60         return max(qmax(id*2,l,mid),qmax(id*2+1,mid+1,r));
 61 }
 62 int main()
 63 {
 64     int n,m,q,b,c,val;
 65     scanf("%d%d",&n,&m);
 66     build(1,1,n);
 67     for (int i=1;i<=n;i++)
 68     {
 69         scanf("%d",&val);
 70         change(1,i,val);
 71     }
 72     for (int i=0;i<m;i++)
 73     {
 74         scanf("%d%d%d",&q,&b,&c);
 75         switch (q)
 76         {
 77             case 1:
 78                 change(1,b,c);
 79             break;
 80             case 2:
 81                 printf("%d
",qsum(1,b,c));
 82             break;
 83             case 3:printf("%d
",qmax(1,b,c));
 84             break;
 85         }
 86     }
 87 
 88  return 0;
 89 }
 90 
 91 /*
 92 4 3
 93 1 2 3 4
 94 2 1 3
 95 1 4 3
 96 3 1 4
 97 */
 98 
 99 /*
100 6
101 3
102 */