区间子段和

这里只考虑区间最大子段和

例题

洛谷SP1043(不带修)洛谷SP1716(带修)

GSS1 - Can you answer these queries I - 洛谷

\(n\) 个数, \(m\) 次操作

每次操作, 查询区间 \([L,R]\) 的最大子段和.

考虑到用线段树维护区间子段和.

对于两个区间合并, 一共有三种情况.

① 最大子段和完全在左侧区间, 这个时候就是左侧区间的最大子段和.

② 最大子段和完全在右侧区间, 这个时候就是右侧区间的最大子段和.

③ 最大子段和跨越两个区间, 这个时候需要左侧区间右侧的最大子段和和右侧区间左侧的最大子段和.

考虑维护这两个变量, 当区间合并时.

左侧的最大子段和可以是左侧区间左侧的最大子段和, 也可以是左侧区间加上右侧区间左侧的最大子段和.

右侧的最大子段和可以是右侧区间右侧的最大子段和，也可以是右侧区间加上左侧区间右侧的最大子段和.

这个时候我们需要多维护一个变量, 即区间和.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 50005;
struct Node {
    i64 Lmx, Rmx, mx, sum;
} tr[N << 2];
Node merge(Node x, Node y) {
    return {max<i64>(x.Lmx, x.sum + y.Lmx), 
            max<i64>(y.Rmx, y.sum + x.Rmx), 
            max<i64>({x.mx, y.mx, x.Rmx + y.Lmx}),
            x.sum + y.sum};
}
void pushup(int p) {
    tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
int a[N];
void build(int p, int L, int R) {
    if (L == R) {
        tr[p] = {a[L], a[L], a[L], a[L]};
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    pushup(p);
}
Node rangeQuery(int p, int L, int R, int QL, int QR) {
    if (QL <= L && R <= QR) {
        return tr[p];
    }
    int mid = L + R >> 1;
    if (QR <= mid) return rangeQuery(p << 1, L, mid, QL, QR);
    if (QL >= mid + 1) return rangeQuery(p << 1 | 1, mid + 1, R, QL, QR);
    return merge(rangeQuery(p << 1, L, mid, QL, QR), rangeQuery(p << 1 | 1, mid + 1, R, QL, QR));
}
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        cout << rangeQuery(1, 1, n, L, R).mx << "\n";
    }
    return 0;
}

GSS3 - Can you answer these queries III - 洛谷

\(n\) 个数, \(m\) 次操作

每次操作,

操作二, 修改 \(a_x\) 为 \(y\).

操作一, 查询区间 \([L,R]\) 的最大子段和.

在不带修的版本加一个单点修改即可.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 50005;
struct Node {
    i64 Lmx, Rmx, mx, sum;
} tr[N << 2];
Node merge(Node x, Node y) {
    return {max<i64>(x.Lmx, x.sum + y.Lmx), 
            max<i64>(y.Rmx, y.sum + x.Rmx), 
            max<i64>({x.mx, y.mx, x.Rmx + y.Lmx}),
            x.sum + y.sum};
}
void pushup(int p) {
    tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
int a[N];
void build(int p, int L, int R) {
    if (L == R) {
        tr[p] = {a[L], a[L], a[L], a[L]};
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    pushup(p);
}
void modify(int p, int L, int R, int pos, int k) {
    if (L == R) {
        a[pos] = k;
        tr[p] = {k, k, k, k};
        return;
    }
    int mid = L + R >> 1;
    if (pos <= mid) modify(p << 1, L, mid, pos, k);
    else modify(p << 1 | 1, mid + 1, R, pos, k);
    pushup(p);
}
Node rangeQuery(int p, int L, int R, int QL, int QR) {
    if (QL <= L && R <= QR) {
        return tr[p];
    }
    int mid = L + R >> 1;
    if (QR <= mid) return rangeQuery(p << 1, L, mid, QL, QR);
    if (QL >= mid + 1) return rangeQuery(p << 1 | 1, mid + 1, R, QL, QR);
    return merge(rangeQuery(p << 1, L, mid, QL, QR), rangeQuery(p << 1 | 1, mid + 1, R, QL, QR));
}
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        int op, L, R;
        cin >> op >> L >> R;
        if (op == 1) {
            cout << rangeQuery(1, 1, n, L, R).mx << "\n";
        } else {
            modify(1, 1, n, L, R);
        }
    }
    return 0;
}

习题

洛谷SP1557洛谷SP2916洛谷SP4487洛谷SP6779CF280D

GSS2 - Can you answer these queries II - 洛谷

\(n\) 个数, \(m\) 次操作

每次操作, 查询区间 \([L,R]\) 的最大子段和(相同的权值只能算一次, 且可选择空段).

离线查询, 按 \(R\) 排序, 我们每次插入 \(a_i\), 然后查询以 \(i\) 为右端点的答案.

使用线段树维护左端点固定的前缀最大子段和和历史最大子段和.

代码

C++
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 100005;
struct Node {
    i64 mx, hmx;
} tr[N << 2];
i64 tagmx[N << 2], taghmx[N << 2];
int a[N];
Node merge(Node x, Node y) {
    return {
        max(x.mx, y.mx),
        max(x.hmx, y.hmx)
    };
}
void pushup(int p) {
    tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
void pushtag(int p, i64 lazymx, i64 lazyhmx) {
    tr[p].hmx = max(tr[p].hmx, tr[p].mx + lazyhmx);
    taghmx[p] = max(taghmx[p], tagmx[p] + lazyhmx);
    tr[p].mx += lazymx;
    tagmx[p] += lazymx;

}
void pushdown(int p) {
    pushtag(p << 1, tagmx[p], taghmx[p]);
    pushtag(p << 1 | 1, tagmx[p], taghmx[p]);
    tagmx[p] = taghmx[p] = 0;
}
void modify(int p, int L, int R, int QL, int QR, i64 k) {
    if (QL <= L && R <= QR) {
        pushtag(p, k, k);
        return;
    }
    pushdown(p);
    int mid = L + R >> 1;
    if (QL <= mid) modify(p << 1, L, mid, QL, QR, k);
    if (QR > mid) modify(p << 1 | 1, mid + 1, R, QL, QR, k);
    pushup(p);
}
Node query(int p, int L, int R, int QL, int QR) {
    if (QL <= L && R <= QR) {
        return tr[p];
    }
    pushdown(p);
    int mid = L + R >> 1;
    if (QR <= mid) return query(p << 1, L, mid, QL, QR);
    if (QL > mid) return query(p << 1 | 1, mid + 1, R, QL, QR);
    return merge(query(p << 1, L, mid, QL, QR), query(p << 1 | 1, mid + 1, R, QL, QR));
}
vector<array<int, 2>> vec[N];
int ans[N];
int last[N];
int main() {
    int n;
    cin >> n;
    vector<int> idx(1, -1000000000);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    int m;
    cin >> m;
    for (int i = 1 ; i <= m ; i++) {
        int L, R;
        cin >> L >> R;
        vec[R].push_back({L, i});
    }
    for (int i = 1 ; i <= n ; i++) {
        modify(1, 1, n, last[a[i]] + 1, i, idx[a[i]]);
        for (auto &[L, idx] : vec[i]) {
            ans[idx] = query(1, 1, n, L, i).hmx;
        }
        last[a[i]] = i;
    }
    for (int i = 1 ; i <= m ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

GSS5 - Can you answer these queries V - 洛谷

GSS6 - Can you answer these queries VI - 洛谷

GSS7 - Can you answer these queries VII - 洛谷

Problem - D - Codeforces