进阶数据结构应用-你能回答这些问题吗

题目-你能回答这些问题吗

问题分析

两个操作

• 求最大连续字段和
• 单点修改序列的一个位置

假设如下定义结构体

struct Node {
   
    int l, r;
    LL maxv;
} tr[N << 2];

因为结果的最大子段和是可能跨区间存在的, 因此只记录一个最大字段和属性是不够的

那么维护跨区间的最大子段和情况需要两个信息, 最大后缀和和最大前缀和

那么问题变成了, 计算当前位置的最大前缀(后缀)是否能通过两个子节点计算得出?
分为两种情况

• 最大前缀没跨段, 那就是左儿子的最大前缀, $l.lmax$
• 最大前缀跨段, 需要的是左儿子的区间和 + 右儿子的最大前缀和

因此还需要记录区间和信息, 那么问题又变成了, 当前段的区间和是否能通过左右两个儿子计算得出, 答案是显然可以的

tr[u].sum = tr[l_son].sum + tr[r_son].sum;

因此如下设计线段树记录的信息

struct Node {
   
    int l, r;
    LL maxv;
    LL lmax, rmax;
    LL sum;
} tr[N << 2];

算法步骤

• 初始化线段树
• 实现上述求最大子段和的操作
• 注意在区间查询的时候, 需要进行分类讨论
• 在递归结束后push up

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 500010;

int n, m, w[N];
struct Node {
   
    int l, r;
    LL maxv;
    LL lmax, rmax;
    LL sum;
} tr[N << 2];

void init(Node &u) {
   
    u = {
   0, 0, 0, 0, 0, 0};
}

void pushup(Node &u, Node &ls, Node &rs) {
   
    u.sum = ls.sum + rs.sum;
    u.lmax = max(ls.lmax, ls.sum + rs.lmax);
    u.rmax = max(rs.rmax, rs.sum + ls.rmax);
    u.maxv = max({
   ls.maxv, rs.maxv, ls.rmax + rs.lmax});
}

void pushup(int u) {
   
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) {
   
    if (l == r) {
   
        tr[u] = {
   l, r, w[l], w[l], w[l], w[l]};
        return;
    }

    tr[u] = {
   l, r, 0, 0, 0, 0};

    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int x, LL val) {
   
    if (tr[u].l == tr[u].r) {
   
        tr[u] = {
   tr[u].l, tr[u].r, val, val, val, val};
        return;
    }

    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) modify(u << 1, x, val);
    if (x > mid) modify(u << 1 | 1, x, val);

    pushup(u);
}

Node query(int u, int ql, int qr) {
   
    if (tr[u].l >= ql && tr[u].r <= qr) return tr[u];

    int mid = tr[u].l + tr[u].r >> 1;
    if (qr <= mid) return query(u << 1, ql, qr);
    // 这里注意是>而不是>=
    if (ql > mid) return query(u << 1 | 1, ql, qr);

    Node ans;
    init(ans);

    Node ls = query(u << 1, ql, qr);
    Node rs = query(u << 1 | 1, ql, qr);
    pushup(ans, ls, rs);
    pushup(u);

    return ans;
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    build(1, 1, n);

    while (m--) {
   
        int k;
        cin >> k;
        if (k == 1) {
   
            int l, r;
            cin >> l >> r;
            if (l > r) swap(l, r);
            Node ans = query(1, l, r);
            cout << ans.maxv << '\n';
        }
        else {
   
            int x, val;
            cin >> x >> val;
            modify(1, x, val);
        }
    }

    return 0;
}