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

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

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