c++线段树之单点修改区间最大子段和-----P4513 小白逛公园

题目大意

• 单点修改
• 查询区间最大字段和

解题思路

如果线段树节点存储的是‘区间最大子段和’，如何合并？
简单的加法或求极值都不行，仔细分析可得，父节点最大字段和可能为：

• 左子树最大子段和
• 右子树最大子段和
• 左子树最大后缀和+右子树最大前缀和

数据结构

线段树存储：

• 区间总和
• 区间最大前缀和
• 区间最大后缀和
• 区间最大子段和

实现细节

合并操作：在构建和更新线段树时，合并左右子节点的信息，以维护当前节点的四个值。

查询操作：递归查询区间，合并结果时考虑左右子区间的不同情况，确保正确计算最大子段和。

// P4513 小白逛公园, 单点修改，区间查最大子段和
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define INF 1000000000
#define MANX 2000002
#define lson (root*2)
#define rson (root*2+1)struct Node {int total; // 区间和int prefix; // 最大前缀和int suffix; // 最大后缀和int max_sum; // 最大字段和
} sgmt[MANX];void push_up(int root) {sgmt[root].total = sgmt[lson].total + sgmt[rson].total;sgmt[root].prefix = max(sgmt[lson].prefix, sgmt[lson].total+sgmt[rson].prefix);sgmt[root].suffix = max(sgmt[rson].suffix, sgmt[rson].total+sgmt[lson].suffix);sgmt[root].max_sum = max({sgmt[lson].max_sum, sgmt[rson].max_sum, sgmt[lson].suffix+sgmt[rson].prefix});
}void update(int a, int b, int l, int r, int root) {if (l == r) {sgmt[root].total = sgmt[root].prefix = sgmt[root].suffix = sgmt[root].max_sum = b;return;}int mid = (l+r)/2;if (a <= mid)  update(a,b,l,mid,lson);else update(a,b,mid+1,r,rson);push_up(root);
}Node query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];Node left = {0,-INF,-INF,-INF}, right = {0,-INF,-INF,-INF};int mid = (l+r)/2;if (a <= mid) left = query(a,b,l,mid,lson);if (b > mid) right = query(a,b,mid+1,r,rson);if (left.max_sum == -INF) return right;if (right.max_sum == -INF) return left;Node merged;merged.total = left.total + right.total;merged.prefix = max(left.prefix, left.total+right.prefix);merged.suffix = max(right.suffix, right.total+left.suffix);merged.max_sum = max({left.max_sum, right.max_sum, left.suffix+right.prefix});return merged;
}void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l, mid, lson);build(mid+1, r, rson);push_up(root);
}int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int n, m; cin >> n >> m;int npot = 1<<(int)ceil(log2(n));for (int i = 0; i < npot; ++i)if (i < n) {cin >> sgmt[npot+i].total;sgmt[npot+i].prefix = sgmt[npot+i].suffix = sgmt[npot+i].max_sum = sgmt[npot+i].total;} else {sgmt[npot+i].prefix = sgmt[npot+i].suffix = sgmt[npot+i].max_sum = -INF; // 无效值}int left = 1, right = npot, root = 1;build(left, right, root);while (m--) {int op, a, b;cin >> op >> a >> b;if (op == 1) {if (a > b) swap(a, b);Node res = query(a, b, left, right, root);cout << res.max_sum << '\n';} else {update(a, b, left, right, root);}}return 0;