<学习笔记> 线段树

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

例题：codevs 4927 线段树练习5

题面

1 有n个数和5种操作： 
2 add a b c：把区间[a,b]内的所有数都增加c 
3 set a b c：把区间[a,b]内的所有数都设为c 
4 sum a b：查询区间[a,b]的区间和 
5 max a b：查询区间[a,b]的最大值 
6 min a b：查询区间[a,b]的最小值

输入描述 Input Description

1 第一行两个整数n，m，第二行n个整数表示这n个数的初始值
2 接下来m行操作，同题目描述

输出描述 Output Description

1 对于所有的sum、max、min询问，一行输出一个答案

样例输入 Sample Input

1 10 6
2 3 9 2 8 1 7 5 0 4 6
3 add 4 9 4
4 set 2 6 2
5 add 3 8 2
6 sum 2 10
7 max 1 7
8 min 3 6

样例输出 Sample Output

1 49
2 11
3 4

数据范围及提示 Data Size & Hint

1 10%:1<n,m<=10
2 30%:1<n,m<=10000
3 100%:1<n,m<=100000
4 保证中间结果在long long(C/C++)、int64(pascal)范围内

代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 using namespace std;
  7 #define ll long long
  8 #define Maxn 100010
  9 
 10 ll N,M,a,b,c;
 11 ll num[Maxn];
 12 string s;
 13 
 14 struct leaf{
 15     ll l,r,add,sum,maxn,minn,flag;
 16 }Tree[Maxn<<2];
 17 
 18 void Dodata(ll n)
 19 {
 20     Tree[n].sum=Tree[n<<1].sum+Tree[n<<1|1].sum;
 21     Tree[n].maxn=max(Tree[n<<1].maxn,Tree[n<<1|1].maxn);
 22     Tree[n].minn=min(Tree[n<<1].minn,Tree[n<<1|1].minn);
 23 }
 24 void DoSet(ll n,ll add)
 25 {
 26     Tree[n].add=add;
 27     Tree[n].minn=Tree[n].maxn=add;
 28     Tree[n].sum=(Tree[n].r-Tree[n].l+1)*add;
 29 }
 30 void Doadd(ll n,ll add)
 31 {
 32     Tree[n].add+=add;
 33     Tree[n].minn+=add;
 34     Tree[n].maxn+=add;
 35     Tree[n].sum+=(Tree[n].r-Tree[n].l+1)*add;
 36 }
 37 void Build(ll n,ll l,ll r)
 38 {
 39      Tree[n].l=l,Tree[n].r=r;
 40      if(l==r)
 41      {
 42           Tree[n].sum=Tree[n].maxn=Tree[n].minn=num[l];
 43           return ;
 44      }
 45      ll mid=(l+r)>>1;
 46      Build(n<<1,l,mid);
 47      Build(n<<1|1,mid+1,r);
 48      Dodata(n);
 49 }
 50 void Spread(int n)
 51 {
 52     ll &ad=Tree[n].add;
 53     if(Tree[n].flag)
 54     {
 55         Tree[n].flag=0;
 56         Tree[n<<1].flag=Tree[n<<1|1].flag=1;
 57         DoSet(n<<1,ad),DoSet(n<<1|1,ad);
 58         ad=0;
 59         return ;
 60     }
 61     Doadd(n<<1,ad);
 62     Doadd(n<<1|1,ad);
 63     ad=0;
 64 }
 65 void Add(ll n,ll l,ll r,ll add)
 66 {
 67      ll L=Tree[n].l,R=Tree[n].r;
 68      if(l<=L&&r>=R)
 69      {
 70             Doadd(n,add);
 71             return ;
 72      }
 73      Spread(n);
 74      ll mid=(L+R)>>1;
 75      if(l<=mid) Add(n<<1,l,r,add);
 76      if(r>mid)  Add(n<<1|1,l,r,add);
 77      Dodata(n);
 78 }
 79 void Set(ll n,ll l,ll r,ll add)
 80 {
 81      ll L=Tree[n].l,R=Tree[n].r;
 82      if(l<=L&&r>=R)
 83      {
 84             Tree[n].flag=1;
 85          DoSet(n,add);
 86             return ;
 87      }
 88      Spread(n);
 89      ll mid=(L+R)>>1;
 90      if(l<=mid) Set(n<<1,l,r,add);
 91      if(r>mid)  Set(n<<1|1,l,r,add);
 92      Dodata(n);
 93 }
 94 ll Ask_Sum(ll n,ll l,ll r)
 95 {
 96      ll L=Tree[n].l,R=Tree[n].r;
 97      if(l<=L&&r>=R)
 98             return Tree[n].sum;
 99      Spread(n);
100      ll mid=(L+R)>>1;
101      ll Ans=0;
102      if(l<=mid) Ans+=Ask_Sum(n<<1,l,r);
103      if(r>mid)  Ans+=Ask_Sum(n<<1|1,l,r);
104      return Ans;
105 }
106 ll Ask_Max(ll n,ll l,ll r)
107 {
108      ll L=Tree[n].l,R=Tree[n].r;
109      if(l<=L&&r>=R)
110          return Tree[n].maxn;
111      Spread(n);
112      ll mid=(L+R)>>1;
113      ll Ans=-(1e9+7);
114      if(l<=mid) Ans=max(Ans,Ask_Max(n<<1,l,r));
115      if(r>mid)  Ans=max(Ans,Ask_Max(n<<1|1,l,r));
116      return Ans;
117 }
118 ll Ask_Min(ll n,ll l,ll r)
119 {
120      ll L=Tree[n].l,R=Tree[n].r;
121      if(l<=L&&r>=R)
122          return Tree[n].minn;
123      Spread(n);
124      ll mid=(L+R)>>1;
125      ll Ans=1e9+7;
126      if(l<=mid) Ans=min(Ans,Ask_Min(n<<1,l,r));
127      if(r>mid)  Ans=min(Ans,Ask_Min(n<<1|1,l,r));
128      return Ans;
129 }
130 int main()
131 {
132     scanf("%lld%lld",&N,&M);
133     for(int i=1;i<=N;++i)
134        scanf("%lld",&num[i]);
135     Build(1,1,N);
136     while(M--)
137     {
138         cin>>s;
139         if(s=="add")  scanf("%lld%lld%lld",&a,&b,&c),
140                       Add(1,a,b,c);
141         if(s=="set")  scanf("%lld%lld%lld",&a,&b,&c),
142                       Set(1,a,b,c);
143         if(s=="sum")  scanf("%lld%lld",&a,&b),
144                       printf("%lld
",Ask_Sum(1,a,b));
145         if(s=="max")  scanf("%lld%lld",&a,&b),
146                       printf("%lld
",Ask_Max(1,a,b));
147         if(s=="min")  scanf("%lld%lld",&a,&b),
148                       printf("%lld
",Ask_Min(1,a,b));
149     }
150     return 0;
151 }