线段树的应用

线段树是一种非常灵活的数据结构，可以沿着许多不同的方向进行变化和扩展。下面尝试对这些扩展进行分类。

有些时候，修改线段树以计算不同类型的查询非常简单，例如把求和改成求最小值或最大值；但有些扩展也可能非常复杂。

求最大值

稍微修改一下前面问题的条件：不再查询区间和，而是查询区间最大值。

线段树的结构与前面描述的完全相同。只需要修改 build 和 update 函数中 $t[v]$ 的计算方式。

现在， $t[v]$ 保存对应区间中的最大值。同时还需要修改 sum 函数中返回值的计算方式，把加法改成求最大值。

当然，这个问题也很容易改成求最小值。

这里不再给出这个问题的实现，因为后面会给出这个问题的一个更复杂版本。

求最大值以及最大值出现的次数

这个问题与上一个问题非常相似。除了求最大值之外，还要计算最大值出现的次数。

为了解决这个问题，我们在线段树的每个节点中保存一对数值：

最大值；
这个最大值在对应区间中出现的次数。

利用两个子节点中保存的信息，仍然可以在常数时间内确定应该保存到 $t[v]$ 中的正确数对。

合并两个这样的数对应该单独写成一个函数，因为：

构建线段树时需要执行这个操作；
回答最大值查询时需要执行这个操作；
修改元素时同样需要执行这个操作。

pair<int, int> t[4*MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first) return a;
    if (b.first > a.first) return b;
    return {a.first, a.second + b.second};
}

void build(int p, int l, int r) {
    if (l == r) {
        t[p] = {a[l], 1};
        return;
    }  
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p] = combine(t[p * 2], t[p * 2 + 1]);
}

pair<int, int> get_max(int p, int l, int r, int x, int y) {
    if (y <= l || x > r) return make_pair(-INF, 0);
    if (x <= l && y >= r) return t[p];
    int mid = (l + r) / 2;
    return combine(get_max(p*2, l, mid, x, y), get_max(p*2+1, mid + 1, r, x, y));
}

void update(int p, int l, int r, int x, int v) { // A[x] 修改为 v
    if (l == r) {
        t[p] = {v, 1};
        return;
    } 

    int mid = (l + r) / 2;
    if (x <= mid) update(p*2, l, mid, x, v);
    else update(p*2+1, mid + 1, r, x, v);
    t[v] = combine(t[p*2], t[p*2+1]);
}

计算最大公约数／最小公倍数

这个问题要求计算数组给定区间中所有数的 GCD／LCM。

这种有趣的线段树变形，可以用与求和／最小值／最大值线段树完全相同的方法解决。

只需要在树的每一个节点中保存对应区间的 GCD／LCM。

合并两个节点时，计算两个节点值的 GCD／LCM 即可。

求最大子段和

这里每次查询仍然给定一个区间

a[l\dots r),

但这一次需要找到一个子区间

a[l'\dots r')

满足

l\le l',\qquad r'\le r,

并使这个子区间内元素的和最大。

与之前一样，我们还希望能够修改数组中的单个元素。

数组中的元素可以是负数，并且最优子区间可以为空，例如当所有元素都为负数时。

这是线段树的一种并不简单的应用。

这一次，我们在每个节点中保存四个值：

对应区间的元素总和；
最大前缀和；
最大后缀和；
该区间的最大子段和。

换句话说，对线段树中的每一个区间，不仅已经预先计算出了这个区间的答案，还预先计算了与这个区间左边界和右边界相接的子区间的答案。

如何用这些数据构建线段树？

还是使用递归方法：

首先计算左子节点和右子节点的四个值，然后把它们合并，得到当前节点的四个值。

注意，当前节点的答案一定属于以下三种情况之一：

左子节点的答案，即最优子区间完全位于左子节点对应的区间中；
右子节点的答案，即最优子区间完全位于右子节点对应的区间中；
左子节点的最大后缀和，加上右子节点的最大前缀和，即最优子区间同时跨越左右两个子节点。

因此，当前节点的答案就是这三个值中的最大值。

计算最大前缀和和最大后缀和甚至更加简单。

下面是 combine 函数的实现。

它只接收左右两个子节点的数据，然后返回当前节点的数据。

struct data {
    int sum, pref, suff, ans;
};

data combine(data l, data r) {
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}

利用 combine 函数，很容易构建线段树。

可以与前面的实现完全相同。

为了初始化叶子节点，我们额外创建辅助函数 make_data，它返回保存单个值信息的 data 对象。

data make_data(int val) {
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(0, val);
    return res;
}
void build(int a[], int v, int tl, int tr) {
    if (tr - tl == 1) {
        t[v] = make_data(a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tr - tl == 1) {
        t[v] = make_data(new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos < tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

剩下的问题就是如何计算查询答案。

和以前一样，我们向下遍历线段树，将查询区间拆分成若干个与线段树节点区间完全一致的子区间，然后将这些子区间的答案合并成查询的最终答案。

因此可以看出，这个过程与最简单线段树的查询完全相同，只不过不再对值进行求和／取最小值／取最大值，而是使用 combine 函数。

data query(int v, int tl, int tr, int l, int r) {
    if (r <= tl || tr <= l)
        return make_data(0);
    if (l <= tl && tr <= r)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(query(v*2, tl, tm, l, r),
                   query(v*2+1, tm, tr, l, r));
}

求最大值​

求最大值以及最大值出现的次数​

计算最大公约数／最小公倍数​

求最大子段和

求最大值

求最大值以及最大值出现的次数

计算最大公约数／最小公倍数