时隔多日，我终于又回来了！
这几天我学习几个高级数据结构，来和大家分享一下线段树。
线段树，名字好高级啊，是不是非常难学？我个人觉得吧，线段树只要明白原理，记熟模板，做题还是比较容易的。QwQ
OK，我们切入正题。
NO.1 what is 线段树
看图理解一下（图片还是比较形象的）
简单线段树结构图
这个东西就是个二叉树，它是一种特殊的二叉树，每个子节点都是一个区间，也可以近似的看做线段，so，他的名字就叫线段树了！
ok，了解完线段树的概念后，是不是会有疑问：它是干啥的？别急，接着看。
No.2 how to use 线段树
首先我们先不说去解决那些问题，我们先说说基础的。
（1）建立一棵线段树
树形结构要考虑如何建立以及存储这个结构，线段树也不例外。
因为是二叉树，所以建树方法肯定也不会太难，没错，看代码：
void build(int p,int l,int r)//其实就是建一棵二叉树
{
lazy[p]=0;
if (l==r)
{
tree[p]=a[l];
return;
}
int mid=(r+l)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree[p]=tree[p<<1]+tree[p<<1|1];
}
当然建立的时候要考虑空间，因为这棵线段树可能不是满二叉树，空间却要补齐满二叉树，所以要开到叶子结点输得4倍（保险起见）。
（2）懒惰标记及其下放操作
相信大家看到上面建树的时候有一个lazy数组？这是做什么用的？
这就是懒惰标记，它在区间修改时会用到
线段树上区间修改时一个一个改肯定会超时，那怎么办，没错，就要用到懒惰标记。
举个形象点的例子，就是你过年时许多亲戚给你压岁钱，你父母帮你一个一个存着，然后你向父母询问的时候，他们就会把所有的钱给你（这例子是比较形象，就是不太现实）。
那我们肯定要下传懒惰标记，用代码如何实现，look this：
void push_down(ll node, ll st, ll ed) {
if (lazy[node] == 0) {
return;
}
ll l_node = node << 1;
lazy[l_node] += lazy[node];
tree[l_node] += lazy[node] * st;
ll r_node = node << 1 | 1;//分别下传到左右两边子节点
lazy[r_node] += lazy[node];
tree[r_node] += lazy[node] * ed;
lazy[node] = 0;
}
（3）单点修改
会了前两个，那我们来点实用性高的技巧，单点修改。
就是找到这个点，然后对它进行操作。
其实操作比较简单，以加法为例，代码如下：
void updata(ll node, ll l, ll r, ll pos, ll val)
{
if (l == r)
{
a[pos] = val;
tree[node] = val;
return;
}
ll mid = (l + r) >> 1；
if (pos <= mid)
{
updata(node << 1, l, mid, pos, val);
}
else
{
updata((node << 1) + 1, mid + 1, r, pos, val);
}
tree[node] = tree[node << 1] + tree[(node << 1) + 1];
}
（4）单点查询
就是直接二分查找就OK了
其实操作也比较简单，代码如下：
ll query(ll node, ll l, ll r, ll rl, ll rr) {
if (rl <= l && r <= rr) {
return tree[node];
}
ll res = 0;
ll mid = (l + r) >> 1;
if (rl <= mid) {
res += query(node << 1, l, mid, rl, rr);
}
if (mid < rr) {
res += query((node << 1) + 1, mid + 1, r, rl, rr);
}
return res;
}
（5）区间修改
这个时候就用到懒惰标记了。
据说懒惰标记这个东西的操作是线段树最精华的部分，懒惰标记下传后就是简单地修改了。
this is code：
void update(ll node,ll st,ll ed,ll l,ll r,ll val)
{
if (l<=st&&ed<=r)
{
lazy[node]+=val;
tree[node]+=val*(ed-st+1);
return;
}
ll mid=(st+ed)>>1;
push_down(node,mid-st+1,ed-mid);
if (l<=mid)
{
update(node<<1,st,mid,l,r,val);
}
if (r>mid)
{
update(node<<1|1,mid+1,ed,l,r,val);
}
tree[node]=tree[node<<1]+tree[node<<1|1];
}
（6）区间查询
这个一般是求区间的和，还是比较简单的。
求个和即可。
代码如下：
ll query(ll node,ll l,ll r,ll rl,ll rr)
{
if(rl<=l&&r<=rr)
{
return tree[node];
}
ll res=0;
ll mid=(l+r)>>1;
if(rl<=mid)
{
res+=query(node<<1,l,mid,rl,rr);
}
if(mid<rr)
{
res+=query((node<<1)+1,mid+1,r,rl,rr);
}
return res;
}
No.3 practice
只说不做可不行，这里推荐几个题目以供大家练习。
1 P3374 【模板】树状数组 1
因为Luogu上板子题少，所以用树状数组的板子来练习线段树，内容是单点修改，区间查询。
2 P3368 【模板】树状数组 2
这道题的内容是区间修改，单点查询。
3 P3372 【模板】线段树 1
这道题的内容是区间修改，区间查询。
4 P3373 【模板】线段树 2
同样是区间修改，区间查询，但是不仅仅有加上一个数，又有乘一个数，考察懒惰标记如何下放。
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
