@线段树
闲话唠在前面
本来准备看完最最基本线段树,然后做做LeetCode
上的线段树题目,学之前幻想LeetCode
的线段树题目应该只涉及到最基本线段树知识点,但是学完之后,去看题目的时候发现对应的题目涉及到是线段树的骚操作,那只好安心看完视频,再看看博客好了。
线段树
线段树是一棵堆式存储的二叉树,每个结点存储对应区间的信息,相当于是存储区间的一个函数值,例如最大值,和,最大连续和等等,具体的代码其实很灵活,之前看到的线段树之间把每个结点的左右值通过函数传参实现,因为确实是固定的,主要的代码不是很难,下面看java
封装的代码
class Nd {
int l, r;
int sum;
}
class Sgt {
Nd[] tr;
int[] arr;
int n;
public Sgt (int[] arr, int n) {
this.arr = arr; this.n = n;
tr = new Nd[n << 2];
for(int i = 1; i < n << 2; ++i)
tr[i] = new Nd();
build(1, 1, n);
}
public void build(int u, int l, int r) {
tr[u].l = l; tr[u].r = r;
if(l == r) {
tr[u].sum = arr[l];
tr[u].add = 0;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
public void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
public void modify(int u, int x, int v) {
if(x == tr[u].l && x == tr[u].r) {
tr[u].sum = v;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)
modify(u << 1, x, v);
else
modify(u << 1 | 1, x, v);
pushup(u);
}
public int query(int u, int l, int r) {
if(l <= tr[u].l && r >= tr[u].r)
return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid)
res += query(u << 1, l, r);
if(r >= mid + 1)
res += query(u << 1 | 1, l, r);
return res;
}
}
懒标记线段树
懒标记稍复杂,需要考虑区间操作的对于区间维护的信息的变动,同时可以抽象一个操作eval
,每次需要分裂操作的时候,那就pushdown
更新左右儿子结点的信息
class Nd {
int l, r;
int sum, add;
}
class Sgt {
Nd[] tr;
int[] arr;
int n;
public Sgt (int[] arr, int n) {
this.arr = arr; this.n = n;
tr = new Nd[n << 2];
for(int i = 1; i < n << 2; ++i)
tr[i] = new Nd();
build(1, 1, n);
}
public void build(int u, int l, int r) {
tr[u].l = l; tr[u].r = r;
if(l == r) {
tr[u].sum = arr[l];
tr[u].add = 0;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
//这里不涉及到懒标记的事情
public void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
public void modify(int u, int l, int r, int d) {
if(l <= tr[u].l && r >= tr[u].r) {
eval(u, d);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)
modify(u << 1, l, r, d);
if(r >= mid + 1)
modify(u << 1 | 1, l, r, d);
pushup(u);
}
public int query(int u, int l, int r) {
if(l <= tr[u].l && r >= tr[u].r)
return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid)
res += query(u << 1, l, r);
if(r >= mid + 1)
res += query(u << 1 | 1, l, r);
return res;
}
//因为是完全覆盖,所以说加和就是本身区间长度
public void pushdown(int u) {
//这里就是更新对应的eval
eval(u << 1, tr[u].add);
eval(u << 1 | 1, tr[u].add);
tr[u].add = 0;
}
public void eval(int u, int add) {
tr[u].sum += (tr[u].r - tr[u].l + 1) * sum;
tr[u].add += add;
}
}
动态开点线段树
思路很简单,但是没有java
代码参考,只能摸着石头过河,最终终于写出了一版,我的习惯是把左右儿子的信息写到结点里面,其实直接开一个数组存储,同时也抽象出一个nmake
方法,用来开点,其实也可以用动态指针的方式,也就是把左右儿子的直接存到父节点里面
/**
//动态指针
class Nd {
int l, r;
int sum, add;
Nd left, right;
}
**/
//此时动态开点就把儿子信息存到节点里面
class Nd {
int l, r;
int ls, rs;
int sum, add;
}
class Sgt {
Nd[] tr;
int n, cnt;
public Sgt(int n) {
cnt = 1;
tr = new Nd[n << 2];
for(int i = 1; i < n << 2; ++i)
tr[i] = new Nd();
build(1, 0, (int)1e9);
}
//只开一个点
public void build(int idx, int l, int r) {
tr[cnt].l = l; tr[cnt].r = r;
tr[cnt].sum = 0; tr[cnt].add = 0;
}
public void modify(int u, int l, int r, int d) {
if(l <= tr[u].l && r >= tr[u].r) {
eval(u, d);
return;
}
int mid = tr[u].l + tr[u].r >> 1;
nmake(u);
pushdown(u);
if(l <= mid)
modify(tr[u].ls, l, r, d);
if(r >= mid + 1)
modify(tr[u].rs, l, r, d);
pushup(u);
}
public int query(int u, int l, int r) {
if(l <= tr[u].l && r >= tr[u].r)
return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
nmake(u);
pushdown(u);
int res = 0;
if(l <= mid)
res += query(tr[u].ls, l, r);
if(r >= mid + 1)
res += query(tr[u].rs, l, r);
return res;
}
public void nmake(int u) {
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u].ls == 0) {
tr[u].ls = ++cnt;
tr[tr[u].ls].l = tr[u].l;
tr[tr[u].ls].r = mid;
}
if(tr[u].rs == 0) {
tr[u].rs = ++cnt;
tr[tr[u].rs].l = mid + 1;
tr[tr[u].rs].r = tr[u].r;
}
}
public void eval(int u, int add) {
tr[u].sum += (tr[u].r - tr[u].l + 1) * add;
tr[u].add += add;
}
public void pushup(int u) {
tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}
public void pushdown(int u) {
eval(tr[u].ls, tr[u].add);
eval(tr[u].rs, tr[u].add);
tr[u].add = 0;
}
}
例题
acwing
上的就不说了,都比较典型,有的特别简单,有的过于难,下面重点说一说LeetCode
上的系列题目
- https://leetcode.cn/problems/my-calendar-i/
- https://leetcode.cn/problems/my-calendar-ii/
- https://leetcode.cn/problems/my-calendar-iii/
题目都是我的日程表安排n
都可以用线段树来做,主要是没想到直接就是用动态开点线段树
其实维护的信息都比较简单,只维护最大值就可以,然后下面贴一下维护最大值和区间一个结点和两个结点的代码
//区间一个结点和两个结点
class Nd {
int l, r;
int ls, rs;
int c1, c2, add;
public String toString() {
return
" c1:" + c1 +
" c2:" + c2 +
" add:" + add;
}
}
class Sgt {
Nd[] tr;
int cnt;
public Sgt(int n) {
tr = new Nd[n << 2];
cnt = 1;
for(int i = 1; i < n << 2; ++i)
tr[i] = new Nd();
build(1, 0, (int)1e9);
}
public void build(int u, int l, int r) {
tr[cnt].l = l; tr[cnt].r = r;
tr[cnt].c1 = 0; tr[cnt].c2 = 0;
tr[cnt].add = 0;
}
public void pushup(int u) {
tr[u].c1 = tr[tr[u].ls].c1 + tr[tr[u].rs].c1;
tr[u].c2 = tr[tr[u].ls].c2 + tr[tr[u].rs].c2;
}
public void eval(int u, int add) {
//add == 2的情况会被查出来
//因为如果一旦add == 2表示info == 2就是存在的,就不会查
if(add == 0)
return;
if(add == 1) {
tr[u].c2 = tr[u].c1;
tr[u].c1 = tr[u].r - tr[u].l + 1;
tr[u].add += add;
} else if(add == 2){
tr[u].c2 = tr[u].r - tr[u].l + 1;
tr[u].add += add;
}
}
public void pushdown(int u) {
eval(tr[u].ls, tr[u].add);
eval(tr[u].rs, tr[u].add);
tr[u].add = 0;
}
public void nmake(int u) {
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u].ls == 0) {
tr[u].ls = ++cnt;
tr[tr[u].ls].l = tr[u].l;
tr[tr[u].ls].r = mid;
}
if(tr[u].rs == 0) {
tr[u].rs = ++cnt;
tr[tr[u].rs].l = mid + 1;
tr[tr[u].rs].r = tr[u].r;
}
}
public void modify(int u, int l, int r, int d) {
if(l <= tr[u].l && r >= tr[u].r) {
eval(u, d);
return;
}
nmake(u);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)
modify(tr[u].ls, l, r, d);
if(r >= mid + 1)
modify(tr[u].rs, l, r, d);
pushup(u);
}
public Nd query(int u, int l, int r) {
if(l <= tr[u].l && r >= tr[u].r)
return tr[u];
nmake(u);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l >= mid + 1) {
return query(tr[u].rs, l, r);
} else if(r <= mid) {
return query(tr[u].ls, l, r);
} else {
Nd ll = query(tr[u].ls, l, r);
Nd rr = query(tr[u].rs, l, r);
Nd res = new Nd();
res.c1 = ll.c1 + rr.c1;
res.c2 = ll.c2 + rr.c2;
return res;
}
}
}
//最大值
class Nd {
int l, r;
int ls, rs;
int v, add;
}
class Sgt {
Nd[] tr;
int cnt;
public Sgt(int n) {
cnt = 1;
tr = new Nd[n << 2];
for(int i = 1; i < n << 2; ++i)
tr[i] = new Nd();
build(1, 0, (int)1e9);
}
public void build(int u, int l, int r) {
tr[cnt].l = l; tr[cnt].r = r;
tr[cnt].v = 0; tr[cnt].v = 0;
}
public void pushup(int u) {
tr[u].v = Math.max(tr[tr[u].ls].v, tr[tr[u].rs].v);
}
public void eval(int u, int add) {
tr[u].v += add;
tr[u].add += add;
}
public void pushdown(int u) {
eval(tr[u].ls, tr[u].add);
eval(tr[u].rs, tr[u].add);
tr[u].add = 0;
}
public void nmake(int u) {
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u].ls == 0) {
tr[u].ls = ++cnt;
tr[tr[u].ls].l = tr[u].l;
tr[tr[u].ls].r = mid;
}
if(tr[u].rs == 0) {
tr[u].rs = ++cnt;
tr[tr[u].rs].l = mid + 1;
tr[tr[u].rs].r = tr[u].r;
}
}
public void modify(int u, int l, int r, int d) {
if(l <= tr[u].l && r >= tr[u].r) {
eval(u, d);
return;
}
nmake(u);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)
modify(tr[u].ls, l, r, d);
if(r >= mid + 1)
modify(tr[u].rs, l, r, d);
pushup(u);
}
public int query(int u, int l, int r) {
if(l <= tr[u].l && r >= tr[u].r)
return tr[u].v;
nmake(u);
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid)
res = Math.max(res, query(tr[u].ls, l, r));
if(r >= mid + 1)
res = Math.max(res, query(tr[u].rs, l, r));
return res;
}
}