线段树模板(含区间最大(小)值)

概述

线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为 $O (l o g n)$

(0) 定义

1 const int INF = 0x3f3f3f3f;
2 const int MAXN = 50010;
3 int a[MAXN],ans[MAXN<<2],lazy[MAXN<<2];
4 // a[]为原序列信息,ans[]模拟线段树维护区间和,lazy[]为懒惰标记
5 int mx[MAXN<<2],mn[MAXN<<2];
6 // mx[]区间最大值 mn[]区间最小值

(1) 更新结点信息

1 void PushUp(int rt)
2 {
3     ans[rt] = ans[rt<<1] + ans[rt<<1|1];   // 区间和
4     mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);   // 区间最大值
5     mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);   // 区间最小值
6 }

(2) 建树

 1 void Build(int l,int r,int rt)
 2 {
 3     if(l == r)
 4     {
 5         mx[rt] = mn[rt] = ans[rt] = a[l];
 6         return ;
 7     }
 8     int mid = (l+r)>>1;
 9     Build(l,mid,rt<<1);
10     Build(mid+1,r,rt<<1|1);
11     PushUp(rt);
12 }

(3) 下推懒惰标记

 1 void PushDown(int rt,int ln,int rn)   
 2 // ln表示左子树元素结点个数,rn表示右子树结点个数
 3 {
 4     if(lazy[rt])
 5     {
 6         lazy[rt<<1] += lazy[rt];
 7         lazy[rt<<1|1] += lazy[rt];
 8         ans[rt<<1] += lazy[rt]*ln;
 9         ans[rt<<1|1] += lazy[rt]*rn;
10         mx[rt<<1] += lazy[rt];
11         mx[rt<<1|1] += lazy[rt];
12         mn[rt<<1] += lazy[rt];
13         mn[rt<<1|1] += lazy[rt];
14         lazy[rt] = 0;
15     }
16 }

(4) 点更新

 1 void Add(int L,int C,int l,int r,int rt)
 2 {
 3     if(l == r)
 4     {
 5         ans[rt] += C;
 6         return ;
 7     }
 8     int mid = (l+r) >> 1;
 9     PushDown(rt,mid-l+1,r-mid);   // 若既有点更新又有区间更新，需要这句话
10     // 什么叫既有点更新又有区间更新？？？
11     if(L <= mid)
12         Add(L,C,l,mid,rt<<1);
13     else 
14         Add(L,C,mid+1,r,rt<<1|1);
15     PushUp(rt);
16 }

(5) 区间更新

 1 void Update(int L,int R,int C,int l,int r,int rt)
 2 {
 3     if(L <= l && r <= R)
 4     {
 5         ans[rt] += C*(r-l+1);
 6         mx[rt] += C;
 7         mn[rt] += C;
 8         lazy[rt] += C;
 9         return ;
10     }
11     int mid = (l+r)>>1;
12     PushDown(rt,mid-l+1,r-mid);
13     if(L <= mid)
14         Update(L,R,C,l,mid,rt<<1);
15     if(R > mid)
16         Update(L,R,C,mid+1,r,rt<<1|1);
17     PushUp(rt);
18 }

(6) 区间查询

 1 ll Query(int L,int R,int l,int r,int rt)
 2 {
 3     if(L <= l && r <= R)
 4     {
 5         // return mx[rt];
 6         // return mn[rt];
 7         return ans[rt];
 8     }
 9     int mid = (l+r)>>1;
10     PushDown(rt,mid-l+1,r-mid);   // 若更新只有点更新,不需要这句
11     ll ANS = 0;
12     // ll MAX = 0;
13     // ll MIN = INF;
14     if(L <= mid)
15     {
16         ANS += Query(L,R,l,mid,rt<<1);
17         // MAX = max(Query(L,R,l,mid,rt<<1),MAX);
18         // MIN = min(Query(L,R,l,mid,rt<<1),MIN);
19     }
20     if(R > mid)
21     {
22         ANS += Query(L,R,mid+1,r,rt<<1|1);
23         // MAX = max(Query(L,R,mid+1,r,rt<<1|1),MAX);
24         // MIN = min(Query(L,R,mid+1,r,rt<<1|1),MIN);
25     }
26     // return MAX;
27     // return MIN;
28     return ANS;
29 }

(7) 调用函数

建树
$B u i l d (1, n, 1);$

点更新
$A d d (L, C, 1, n, 1);$

若只涉及点更新只需用(1)(2)(4)(6)
若只涉及区间更新需用(1)(2)(3)(5)(6)
若两种更新都有则在所有向子区间查询或更新前都需PushDown()