1. 动态开点 - 估点
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
int N = (int)1e9;
const static int M = 4 * 1e4;
struct Node
{
// 左右儿子的索引, 0表示还未创建
int ls, rs;
// 当前区间的值
int max;
// 懒惰标记
int lazy;
};
Node tr[M] = {{0, 0, 0, 0}};
int cnt = 1;
void update(int p, int s, int t, int l, int r, int val)
{
// p: 当前节点的索引
// [s, t]: 当前节点的区间
// [l, r]: 修改区间
// val: 值
if (l <= s && t <= r)
{
tr[p].max += val;
tr[p].lazy += val;
return;
}
nodecreate(p);
pushdown(p);
int mid = (s + t) >> 1;
if (l <= mid)
{
update(tr[p].ls, s, mid, l, r, val);
}
if (mid < r)
{
update(tr[p].rs, mid + 1, t, l, r, val);
}
pushup(p);
return;
}
void pushdown(int p)
{
// 懒惰标记下放操作
tr[tr[p].ls].max += tr[p].lazy;
tr[tr[p].ls].lazy += tr[p].lazy;
tr[tr[p].rs].max += tr[p].lazy;
tr[tr[p].rs].lazy += tr[p].lazy;
tr[p].lazy = 0;
return;
}
void pushup(int p)
{
// 儿子节点更新父亲节点
tr[p].max = max(tr[tr[p].ls].max, tr[tr[p].rs].max);
return;
}
int query(int p, int s, int t, int l, int r)
{
// p: 当前节点的索引
// [s, t]: 当前节点的区间
// [l, r]: 修改区间
if (l <= s && t <= r)
{
return tr[p].max;
}
nodecreate(p);
pushdown(p);
int mid = (s + t) >> 1;
int ans = 0;
if (l <= mid)
{
ans = query(tr[p].ls, s, mid, l, r);
}
if (mid < r)
{
ans = max(ans, query(tr[p].rs, mid + 1, t, l, r));
}
return ans;
}
void nodecreate(int p)
{
// 创建左右儿子节点
if (tr[p].ls == 0)
{
tr[p].ls = ++cnt;
}
if (tr[p].rs == 0)
{
tr[p].rs = ++cnt;
}
return;
}
2. 注意事项
2.1 估点
动态开点相比于原始的线段树实现, 本质仍是使用「满二叉树」的形式进行存储, 只不过是按需创建区间
如果我们是按照连续段进行查询或插入, 最坏情况下仍然会占到 4 * n 的空间, 因此盲猜 $\log{n}$ 的常数在 4 左右, 保守一点可以直接估算到 6
因此我们可以估算点数为 $6m\log{n}$, 其中 n = 1e9 和 m = 1e4 分别代表值域大小和查询次数
一个比较实用的估点方式可以 「尽可能的多开点数」
2.2 左右儿子索引
动态开点的优势在于, 不需要事前构造空树, 而是在插入操作 add 和查询操作 query 时根据访问需要进行「开点」操作
由于我们不保证查询和插入都是连续的, 因此对于父节点 u 而言, 我们不能通过 u << 1和 u << 1 | 1的固定方式进行访问
而要将节点 tr[u] 的左右节点所在 tr 数组的下标进行存储, 分别记为ls和 rs属性
对于 tr[u].ls=0 和 tr[u].rs=0 则是代表子节点尚未被创建, 当需要访问到它们, 而又尚未创建的时候, 则将其进行创建
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 记录节点的索引
int cnt = 1;
// 动态创建
void nodecreate(int p)
{
// 创建左右儿子节点
if (tr[p].ls == 0)
{
tr[p].ls = ++cnt;
}
if (tr[p].rs == 0)
{
tr[p].rs = ++cnt;
}
return;
}
3. 具体题目具体分析
例题: 218 天际线
update不是给[l, r]加上高度h, 而是取区间的最大值, 才能被叫做天际线 即: 区间整体修改为一个更大的值
pushdown时, 同样是取最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void update(int p, int s, int t, int l, int r, int val)
{
if (l <= s && t <= r)
{
// 这里取高度的最大值
tr[p].max = max(tr[p].max, val);
tr[p].add = max(tr[p].add, val);
return;
}
}
void pushdown(int p)
{
// 向下传递时, 同样传递最大值
tr[tr[p].ls].max = max(tr[tr[p].ls].max, tr[p].add);
tr[tr[p].ls].add = max(tr[tr[p].ls].add, tr[p].add);
tr[tr[p].rs].max = max(tr[tr[p].rs].max, tr[p].add);
tr[tr[p].rs].add = max(tr[tr[p].rs].add, tr[p].add);
tr[p].add = 0;
return;
}
例题: 732 我的日程安排 3
线段树模板题 区间修改: 区间整体增加一个值val
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
30
31
32
33
34
void update(int p, int lc, int rc, int l, int r, int val)
{
// p: 当前节点的编号
// [lc, rc]: 当前节点包含的区间
// [l, r]: 修改区间
// 当前区间是修改区间的子区间
if (l <= lc && rc <= r)
{
tr[p].add += val;
tr[p].max += val;
return;
}
// 如果要访问节点n的孩子节点, 就需要创建其孩子节点
lazycreate(p);
pushdown(p); // 下放数据
int mid = lc + rc >> 1;
if (l <= mid)
update(tr[p].lc, lc, mid, l, r, val);
if (r > mid)
update(tr[p].rc, mid + 1, rc, l, r, val);
pushup(p); // 从子节点更新当前节点数据
return;
}
void pushdown(int p)
{
tr[tr[p].lc].add += tr[p].add;
tr[tr[p].lc].max += tr[p].add;
tr[tr[p].rc].add += tr[p].add;
tr[tr[p].rc].max += tr[p].add;
tr[p].add = 0;
return;
}
4. 离散化
如果一道题是「值域很大」的离线题（提前知晓所有的询问）, 通过「离散化」来进行处理, 将值域映射到一个小空间去, 从而解决 MLE 问题
例如: 218 天际线问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 离散化
set<int> st;
for (int i = 0; i < buildings.size(); i++)
{
st.insert(buildings[i][0]);
st.insert(buildings[i][1]);
}
unordered_map<int, int> mp;
n = 0;
for (auto &num : st)
{
mp[num] = ++n;
}
// cout << st.size() << endl;