28.线段树与树状数组基础

一、线段树

1.区间问题

线段树是一种在算法竞赛中常用来维护区间的数据结构。它思想非常简单，就是借助二叉树的结构进行分治，但它的功能却非常强大，因此在很多类型的题目中都有它的变种，很多题目都需要以线段树为基础进行发展。

具体来讲，线段树可以在 $O(\log N)$ 的时间复杂度内实现单点修改和区间修改，以及动态区间查询、求和、求最大、求区间最小值等操作。

2.基本结构

通常我们会将线段树构建成二叉树的样子，二叉树的每一个结点都表示一段区间，并使用数组来进行简化表示。每一个非叶子结点都有左右两棵子树，分别表示区间的左右两部分。现以根节点在数组中的下标为 $1$ ，则线段树具有以下的性质。

一个结点若其在数组中的下标为 $p os$ ，则它的左右儿子的下标分别为 $2 p os, 2 p os + 1$ 。
一个结点表示的区间为 $[l, r]$ ，则它的左右儿子的表示的区间分别是 $[l, mi d], [mi d + 1, r]$ ，其中 $mi d = (l + r) /2$ 。
线段树的空间一般要开到 $4 n$ ，以防止特殊的越界发生。

例如，以结点总数 $n = 10$ 为例构造的线段树如下所示：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

3.线段树的建立

下面以维护区间最小值为例来讲解线段树的基本操作：

函数包含三个参数，分别表示该结点的下标、左端点、右端点。
如果左端点等于右端点，则说明已经到叶子结点了，它的最小值就是它自己，直接对其赋值并返回。
如果不是叶子结点，那么区间 $[l, r]$ 的最小值就是区间 $[l, mi d], [mi d + 1, r]$ 的最小值的最小值，所以应该递归地先求出子区间的最小值，再最后得到当前的最小值。

ll tree[4*maxn],a[maxn];
void build(ll pos,ll l,ll r)
{
    if(l==r)
    {
        tree[pos]=a[l];
        return;
    }
    ll mid=(l+r)>>1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    tree[pos]=min(tree[pos<<1],tree[pos<<1|1]);
}

建树的时间复杂度为 $O (n)$ 。

4.单点更新

如果这个时候，某一个结点的值被更新了，那么可以考虑这个结点影响了哪些结点，如此只需要在 $O(\log n)$ 的时间就可以完成整棵树的更新了，而不需要花费 $O (n)$ 的时间去重新建树。

思路很简单，我们已知被更新结点的下标，所以只需要判断它在左边还是右边即可，这样每次只选择一边，时间复杂度大大降低。但一定要记住，这里的更新和建树一样，是自下而上更新的，所以结点的值应该在递归的时候更新。

void update(ll pos,ll l,ll r,ll x,ll num)
{
    if(l==r)
    {
        tree[pos]=num;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)
        update(pos<<1,l,mid,x,num);
    else
        update(pos<<1|1,mid+1,r,x,num);
    tree[pos]=min(tree[pos<<1],tree[pos<<1|1]);
}

5.单点查询

和单点更新几乎一致

void query(ll pos,ll l,ll r,ll x)
{
    if(l==r)
        return tree[pos];
    ll mid=(l+r)>>1;
    if(x<=mid)
        return query(pos<<1,l,mid,x);
    else
        return query(pos<<1|1,mid+1,r,x);
}

6.区间查询

因为线段树上的区间划分是固定的，很多时候查询不可能刚好是某一个结点，所以我们需要对区间进行分段，最后依靠递归得到答案。

设我们要查询的区间为 $[s, e]$ ，则到一个结点时可能有三种情况：

若该结点是 $[s, e]$ 的子区间，那么直接返回这个最小值
若该结点的左半区间与 $[s, e]$ 有交集，即存在一段 $[s, x]$ 与 $[l, mi d]$ 有交集，那么只需要满足 $s <= mi d$ 即可，随后查询左侧的最小值
同理，若该结点的右半区间与 $[s, e]$ 有交集，即存在一段 $[x, e]$ 与 $[mi d + 1, r]$ 有交集，那么只需要满足 $e > mi d$ 即可，随后查询右侧的最小值
最后将左右两侧的最小值取最小值，就是当前区间的最小值

ll query(ll pos,ll l,ll r,ll s,ll e)
{
    if(s<=l && r<=e)
        return tree[pos];
    ll mid=(l+r)>>1,ans=inf;
    if(s<=mid)
        ans=min(ans,query(pos<<1,l,mid,s,e));
    if(e>mid)
        ans=min(ans,query(pos<<1|1,mid+1,r,s,e));
    return ans;
}

7.区间更新

假设此时，修改的不只是一个元素的值，比如将某一个区间内的所有值都加上 $k$ ，这个时候就需要区间更新了。如果一个一个更新，无疑是非常糟糕的，还不如重建树。

所以我们可以借助区间查询的思想来进行。但这里有一个问题，区间更新与查询不同，这是会影响到某一整棵子树的值，难道我们要每次都更新到叶子结点吗？

为了优化这一过程，我们引入一个新的数组：懒惰标记。它被定义为当前区间所经历的且还没有向下传递的更新。用以累计这个区间所进行的改变，在需要的时候才向下传递给子结点进行更新。

ll lazy[4*maxn];
void down(ll pos)
{
    if(lazy[pos])
    {
        lazy[pos<<1]+=lazy[pos];
        lazy[pos<<1|1]+=lazy[pos];
        tree[pos<<1]+=lazy[pos];
        tree[pos<<1|1]+=lazy[pos];
        lazy[pos]=0;
    }
}
ll query(ll pos,ll l,ll r,ll s,ll e)
{
    if(s<=l && r<=e)
        return tree[pos];
    down(pos);
    ll mid=(l+r)>>1,ans=inf;
    if(s<=mid)
        ans=min(ans,query(pos<<1,l,mid,s,e));
    if(e>mid)
        ans=min(ans,query(pos<<1|1,mid+1,r,s,e));
    return ans;
}
void update(ll pos,ll l,ll r,ll s,ll e,ll k)
{
    if(s<=l && r<=e)
    {
        lazy[pos]+=k;
        tree[pos]+=k;
        return;
    }
    down(pos);
    ll mid=(l+r)>>1;
    if(s<=mid)
        update(pos<<1,l,mid,s,e,k);
    if(e>mid)
        update(pos<<1|1,mid+1,r,s,e,k);
    tree[pos]=min(tree[pos<<1],tree[pos<<1|1]);
}