线段树模板(结构体写法)-待补全

这个坑先放着吧。。。

概述

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

(0) 定义

1
2
3
4
5
6
7
8
9
10
11
12
13
const int INF = 0x3f3f3f3f;
const int MAXN = 50010;
int a[MAXN];
struct node
{
int l,r;
int lazy;
// 懒标记
int ans,nmax,nmin;
// 区间和 区间最大值 区间最小值
}tree[MAXN<<2];
int ans,nmax,nmin;
// 建树

(1) 更新结点信息

1
2


(2) 建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Build(int rt,int l,int r)
{
tree[rt].l = l;
tree[rt].r = r;
tree[rt].lazy = 0;
if(l == r)
{
tree[rt].ans = tree[rt].nmax = tree[rt].nmin = a[l];
return ;
}
int mid = (l+r)>>1;
Build(rt<<1,l,mid);
Build(rt<<1|1,mid+1,r);
tree[rt].ans = tree[rt<<1].ans+tree[rt<<1|1].ans;
tree[rt].nmax = max(tree[rt<<1].nmax,tree[rt<<1|1].nmax);
tree[rt].nmin = min(tree[rt<<1].nmin,tree[rt<<1|1].nmin);
}

(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
17
18
19
20
void Add(int rt,int l,int r,int add)   // 在结点rt的区间(l,r)上增加add
{
if(tree[rt].l == l && tree[rt].r == r)
{
tree[rt].lazy += add;
return ;
}
tree[rt].ans += add*(r-l+1);
int mid = (tree[rt].l+tree[rt].r)>>1;
if(r <= mid)
Add(rt<<1,l,r,add);
else
if(l > mid)
Add(rt<<1|1,l,r,add);
else
{
Add(rt<<1,l,mid,add);
Add(rt<<1|1,mid+1,r,add);
}
}

(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
ll Query(int rt,int l,int r)
{
if(l == tree[rt].l && r == tree[rt].r)
{
return tree[rt].ans+(r-l+1)*tree[rt].lazy;
}
tree[rt].ans += (tree[rt].r-tree[rt].l+1)*tree[rt].lazy;
int mid = (tree[rt].l + tree[rt].r)>>1;
Add(rt<<1,tree[rt].l,mid,tree[rt].lazy);
Add(rt<<1|1,mid+1,tree[rt].r,tree[rt].lazy);
tree[rt].lazy = 0;
if(r <= mid)
return Query(rt<<1,l,r);
else
if(l > mid)
return Query(rt<<1|1,l,r);
else
{
return Query(rt<<1,l,mid)+Query(rt<<1|1,mid+1,r);
}
}

区间查询(查询区间最值)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Query_m(int rt,int l,int r)
{
if(tree[rt].nmax <= nmax && tree[rt].nmin >= tree[rt].nmin) // 不必再往下找
return ;
if(tree[rt].l == l && tree[rt].r == r)
{
nmax = max(tree[rt].nmax,nmax);
nmin = min(tree[rt].nmin,nmin);
return ;
}
int mid = (tree[rt].l+tree[rt].r)>>1;
if(r <= mid)
Query_m(rt<<1,l,r);
else
if(l > mid)
Query_m(rt<<1|1,l,r);
else
{
Query_m(rt<<1,l,mid);
Query_m(rt<<1|1,mid+1,r);
}
}

(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()$