线段树进阶——信息与标记，历史最值和历史和线段树

· · 算法·理论

前言

听学长讲题，总得写写文章。

线段树的进阶理解：信息与标记

想要将线段树进阶，首先得理解线段树是个什么。

很多人会说“数据结构”“二叉搜索树”等等。然而，学长给出了更好的答案：信息（info）与标记（tag）的统一体。

以最简单的普通线段树为例：维护区间加、区间查询。让我们从信息与标记来理解这棵大家都会写的线段树。

对于这样一颗线段树，它每个节点上要维护：

信息：区间和 sum，区间长度 len。

标记：区间加标记 dplus。

实现一棵线段树，最关键的部分在于哪里？在于 pushup 和 pushdown 两个函数。而这两个函数，本质上实现了以下的操作：

对于两个区间 x,y 并起来：

区间和，就是将它们加起来。即 sum_{x+y}=sum_x+sum_y。

区间长度，也是把它们加起来。即 len_{x+y}=len_x+len_y。

对于一个区间 x 和一个标记 y：

区间和：sum_{x+y}=sum_x+dplus_y\times len_x。

区间长度无需合并。

对于两个标记 x,y：

区间加标记：dplus{x+y}=dplus_x+dplus_y。

事实上，我们在实现这颗简单的线段树时，就是运用了以上三种操作。其中，pushup 是第一种，pushdown 是第二种和第三种。

历史最值线段树

历史最值线段树维护某个区间每个元素在每个历史版本中的最大值的最大值。

简单来说，有两种操作：区间加（可能为负），区间求历史最值。

我们从信息与标记的角度构建这一棵线段树。

对于信息，我们首先需要维护当前区间当前最大值 max 和当前区间历史最大值 \_max。

信息的合并是容易的。只需要将两个区间的两个信息分别取最大值即可。

那么标记呢？看似只需要维护一个区间加标记 dplus。那我们不妨试试看。

信息与标记的合并：max_{x+y}=max_x+dplus_y,\_max_{x+y}=\max(\_max_x,max_x+dplus_y)。

标记与标记的合并：dplus_{x+y}=dplus_x+dplus_y。

看上去很有道理，不过这是错误的。

区间加操作不止包括区间加上一个正数，也包括加上一个负数。假设我们先给某个区间加上一个数，又减去一个数，那么在下传标记时，我们只能记录到最终的加标记，然而在历史上，这些数曾被加上一个更大的数。

所以进行如下修改：标记包括区间加标记 dplus 和历史区间加最值 \_dplus。

信息与标记的合并：max_{x+y}=max_x+dplus_y,\_max_{x+y}=\max(\_max_x,max_x+\_dplus_y)。

标记与标记的合并：dplus_{x+y}=dplus_x+dplus_y,\_dplus_{x+y}=\max(\_dplus_x,dplus_x+\_dplus_y)。

然后就可以维护了。

例题

SP1557 GSS2 - Can you answer these queries II

这种统计某个区间的所有子区间的信息的问题，有时可以使用扫描线+历史最值/和线段树。

例如本题，我们可以考虑对所有询问关于右端点排序，然后枚举右端点。当枚举到 R 时，这颗线段树的元素 i 用来表示区间 [i,R] 的按题意统计的和。那么，对于某个查询的区间 [L,R]，它的答案即为 [L,R] 的历史最值。

这是好想的。右端点从 1 枚举到 R 时，元素 i 维护的值分别是 [i,i],[i,i+1],\dots,[i,R] 的按题意统计和。那么，区间 [L,R] 的历史最值自然就是其所有子区间的按题意统计的和的最大值。

#include <bits/stdc++.h>
#define ll long long
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)

using namespace std;

const int maxn = 1e5 + 5;

ll a[maxn], pre[maxn << 1], ans[maxn];

namespace seg{
struct info{
    ll max, _max;
};
struct tag{
    ll add, _add;
};
inline info operator + (const info &x, const info &y){
    return (info){max(x.max, y.max), max(x._max, y._max)};
}
inline info operator + (const info &x, const tag &y){
    return (info){x.max + y.add, max(x._max, x.max + y._add)};
}
inline tag operator + (const tag &x, const tag &y){
    return (tag){x.add + y.add, max(x._add, x.add + y._add)};
}
struct node{
    info in;
    tag tg;
}t[maxn << 2];

void up(int x){
    t[x].in = t[l(x)].in + t[r(x)].in;
}
void down(int x){
    t[l(x)].in = t[l(x)].in + t[x].tg, t[l(x)].tg = t[l(x)].tg + t[x].tg;
    t[r(x)].in = t[r(x)].in + t[x].tg, t[r(x)].tg = t[r(x)].tg + t[x].tg;
    t[x].tg = (tag){0, 0};
}
void update(int x, int l, int r, int ql, int qr, ll k){
    if(ql <= l && r <= qr){
        tag g = (tag){k, k};
        t[x].in = t[x].in + g, t[x].tg = t[x].tg + g;
        return;
    }
    down(x);
    int mid = l + r >> 1;
    if(ql <= mid) update(l(x), l, mid, ql, qr, k);
    if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);
    up(x);
}
ll query(int x, int l, int r, int ql, int qr){
    if(ql <= l && r <= qr) return t[x].in._max;
    down(x);
    int mid = l + r >> 1;
    ll res = 0;
    if(ql <= mid) res = max(res, query(l(x), l, mid, ql, qr));
    if(qr > mid) res = max(res, query(r(x), mid + 1, r, ql, qr));
    return res;
}}
struct node{
    int l, r, id;
}qs[maxn];

inline bool operator < (const node &x, const node &y){
    return x.r < y.r;
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    int q;
    scanf("%d", &q);
    for(int i = 1; i <= q; i ++){
        scanf("%d %d", &qs[i].l, &qs[i].r);
        qs[i].id = i;
    }
    sort(qs + 1, qs + q + 1);
    int p = 1;
    for(int i = 1; i <= n; i ++){
        ll ra = a[i] + 100000;
        int lt = pre[ra];
        pre[ra] = i;
        seg::update(1, 1, n, lt + 1, i, a[i]);
        while(qs[p].r == i) ans[qs[p].id] = seg::query(1, 1, n, qs[p].l, qs[p].r), p ++;
    }
    for(int i = 1; i <= q; i ++) printf("%lld\n", ans[i]);
    return 0;
}

历史和线段树

历史最值线段树维护某个区间每个元素之和在每个历史版本中的和。