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

概述

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

(0) 定义

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

(1) 更新结点信息

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

(2) 建树

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

(3) 下推懒惰标记

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

(4) 点更新

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

(5) 区间更新

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

(6) 区间查询

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

(7) 调用函数

建树
$Build(1,n,1);$

点更新
$Add(L,C,1,n,1);$
区间修改
$Update(L,R,C,1,n,1);$
区间查询
$ll$ $ANS = Query(L,R,1,n,1);$

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