最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

今日热文：线段树学习笔记

来源：博客园

时隔多日，我终于又回来了！

这几天我学习几个高级数据结构，来和大家分享一下线段树。线段树，名字好高级啊，是不是非常难学？我个人觉得吧，线段树只要明白原理，记熟模板，做题还是比较容易的。QwQOK，我们切入正题。


(相关资料图)

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

No.3 practice

只说不做可不行，这里推荐几个题目以供大家练习。

1 P3374 【模板】树状数组 1

因为Luogu上板子题少，所以用树状数组的板子来练习线段树，内容是单点修改，区间查询。

2 P3368 【模板】树状数组 2

这道题的内容是区间修改，单点查询。

3 P3372 【模板】线段树 1

这道题的内容是区间修改，区间查询。

4 P3373 【模板】线段树 2

同样是区间修改，区间查询，但是不仅仅有加上一个数，又有乘一个数，考察懒惰标记如何下放。

关键词：