首先,知道线段树的基本操作和基本作用:
基本操作:
1. build(构建)
2. pushup(用子节点求父节点)
3. pushdown(懒标记)
4. query(查询)
5. change(修改) — 单点修改和区域修改
基本作用
1. 在某个位置修改一个数
2. 求某一个区间的信息值
然后思考怎么构建线段树:
- 结构体的设定
(1) 左右区间
(2) 信息值:该值要确保能从子节点得到 - 递归建立线段树:
void build(int u , int l , int r)
{
tr[u] = {l,r} // 记录区间
if(l == r) return;
int mid = l + r >> 1;
build(u << 1 , l , mid) , build(u << 1 | 1 , mid + 1 , r);
}
- 结构体数组一般要开四倍