线段树模板

基础线段树模板：

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 
 6 const int maxn=200005;
 7 
 8 int val[maxn+1];
 9 
10 struct node
11 {
12     int max;//需要处理的值
13     int left;
14     int right;
15 }tree[maxn*3];//开三倍就够了
16 
17 int get_max(int x,int y)
18 {
19     if(x>y)
20     return x;
21     else
22     return y;
23 }
24 
25 int creat(int Root,int Left,int Right)//根节点和根节点的左右区间
26 {
27     tree[Root].left=Left;
28     tree[Root].right=Right;//对每个节点定义其左右节点
29     
30     if(Left==Right)//子叶
31     return tree[Root].max=val[Left];//返回的是需要处理值  也就是递归调用的边界
32     
33     int a,b,mid=(Left+Right)>>1;
34     
35     a=creat(Root<<1,Left,mid);
36     b=creat((Root<<1)+1,mid+1,Right);
37     
38     return tree[Root].max=get_max(a,b);//向上一层递归返回该节点的处理值
39     
40     //这样，一个节点的最基本元素，1、节点所拥有的区间 2、节点的处理值
41 }
42 
43 int calculate(int Root,int Left,int Right)
44 {
45     if(tree[Root].left>Right||tree[Root].right<Left)
46     return 0;//没有交集，直接返回一个不会影响结果的无关值
47     
48     if(Left<=tree[Root].left&&tree[Root].right<=Right)
49     return tree[Root].max;//该区间搞好为所求区间的一个子集，可直接返回该区间的处理值
50     
51     int a,b;
52     a=calculate(Root<<1,Left,Right);
53     b=calculate((Root<<1)+1,Left,Right);
54     return get_max(a,b);//向上一层返回得到的处理值
55 }
56 
57 int update(int Root,int pos,int value)//更新表面上看起来只是更新一个点，实际是更新的该店的所有的父节点
58 {
59     if(pos<tree[Root].left||tree[Root].right<pos)
60     return tree[Root].max;//与索要更新的点（区间）没有交集，忽略更新
61     
62     if(tree[Root].left==pos&&tree[Root].right==pos)
63     return tree[Root].max=value;//刚好就是给点
64     
65     int a,b;
66     a=update(Root<<1,pos,value);
67     b=update((Root<<1)+1,pos,value);
68     
69     return tree[Root].max=get_max(a,b);//更新该节点的最新处理值
70 }
71 
72 int main()
73 {
74     int n,m;
75     //freopen("aa.txt","r",stdin);
76     while(scanf("%d %d",&n,&m)!=EOF)
77     {
78         for(int i=1;i<=n;i++)
79         {
80             scanf("%d",&val[i]);
81         }
82         creat(1,1,n);
83         char s;
84         int a,b;
85         while(m--)
86         {
87             getchar();
88             scanf("%c",&s);
89             scanf("%d %d",&a,&b);
90             if(s=='U')
91             update(1,a,b);
92             else
93             printf("%d
",calculate(1,a,b));
94         }
95     }
96     return 0;
97 }

View Code

更新区间值模板（将某个区间全部更新为一个值）

代码：

  1 #include<iostream>
  2 #include<string.h>
  3 #include<stdio.h>
  4 using namespace std;
  5 
  6 const int maxn=100005;
  7 
  8 //int val[maxn+1];
  9 
 10 struct node
 11 {
 12     int mark;
 13     int total;//需要处理的值
 14     int left;
 15     int right;
 16 }tree[maxn*3];//开三倍就够了
 17 
 18 int creat(int Root,int Left,int Right)//根节点和根节点的左右区间
 19 {
 20     tree[Root].mark=0;//未标记
 21     tree[Root].left=Left;
 22     tree[Root].right=Right;//对每个节点定义其左右节点
 23 
 24     if(Left==Right)//子叶
 25     return tree[Root].total=1/*val[Left]*/;//返回的是需要处理值  也就是递归调用的边界
 26 
 27     int a,b,mid=(Left+Right)>>1;
 28 
 29     a=creat(Root<<1,Left,mid);
 30     b=creat((Root<<1)+1,mid+1,Right);
 31 
 32     return tree[Root].total=a+b;//向上一层递归返回该节点的处理值
 33 
 34     //这样，一个节点的最基本元素，1、节点所拥有的区间 2、节点的处理值
 35 }
 36 
 37 void update_mark(int root)
 38 {
 39     if(tree[root].mark)
 40     {
 41         tree[root].total=tree[root].mark*(tree[root].right-tree[root].left+1);//更新该节点的实际值
 42         if(tree[root].left!=tree[root].right)//还存在左右孩子
 43         {
 44             tree[root<<1].mark=tree[root].mark;
 45             tree[root<<1|1].mark=tree[root].mark;
 46         }
 47         tree[root].mark=0;
 48     }
 49 }
 50 
 51 int calculate(int Root,int Left,int Right)
 52 {
 53     update_mark(Root);
 54     if(tree[Root].left>Right||tree[Root].right<Left)
 55     return tree[Root].total;//没有交集，直接返回一个不会影响结果的无关值
 56 
 57     if(Left<=tree[Root].left&&tree[Root].right<=Right){
 58         return tree[Root].total;//该区间搞好为所求区间的一个子集，可直接返回该区间的处理值
 59     }
 60     int a,b;
 61     a=calculate(Root<<1,Left,Right);
 62     b=calculate((Root<<1)+1,Left,Right);
 63     return a+b;//向上一层返回得到的处理值
 64 }
 65 
 66 int update(int Root,int left,int right,int value)//更新表面上看起来只是更新一个点，实际是更新的该店的所有的父节点
 67 {
 68     update_mark(Root);
 69     if(tree[Root].left>right||tree[Root].right<left)
 70     return tree[Root].total;//与索要更新的点（区间）没有交集，忽略更新
 71 
 72     if(tree[Root].left>=left&&tree[Root].right<=right){
 73         tree[Root].mark=value;
 74         return tree[Root].total=tree[Root].mark*(tree[Root].right-tree[Root].left+1);
 75     }
 76     int a,b;
 77     a=update(Root<<1,left,right,value);
 78     b=update((Root<<1)+1,left,right,value);
 79 
 80     return tree[Root].total=a+b;//更新该节点的最新处理值
 81 }
 82 
 83 int main()
 84 {
 85     int t;
 86     //freopen("aa.txt","r",stdin);
 87     scanf("%d",&t);
 88 
 89     for(int kase=1;kase<=t;kase++)
 90     {
 91         int n,m;
 92         scanf("%d %d",&n,&m);
 93         creat(1,1,n);
 94         int a,b,c;
 95         while(m--)
 96         {
 97             scanf("%d %d %d",&a,&b,&c);
 98             update(1,a,b,c);
 99         }
100         printf("Case %d: The total value of the hook is %d.
",kase,calculate(1,1,n));
101     }
102     return 0;
103 }

View Code