线段树维护区间和、最大前缀、最大后缀和最大子段和，支持单点修改。
OJ: luogu
题目 ID: P4513
难度:普及+/提高
标签:线段树最大子段和点修改python
日期: 2026-07-16 23:59
题意
区间查询最大连续子段和，另有单点赋值操作；查询端点可能反向给出。
思路
节点保存 sum、最大前缀 prefix、最大后缀 suffix 和最大子段 best。合并左右节点时，跨中点的候选是 left.suffix + right.prefix，其余三项分别取左右最大值。查询部分区间时返回一个五元组，最后按相同公式合并。
Python 知识
merge返回元组，适合把一个区间的四个统计量和长度作为整体传递。array("q")让四棵大规模 64 位统计数组保持紧凑。- 用
None表示还没有取到左子区间，避免为查询补造无效的负无穷节点。 max的多个参数直接表达三种最大子段来源。
代码
python
import sys
from array import array
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
values = array("q", (int(input()) for _ in range(n)))
total = array("q", [0]) * (4 * n)
prefix = array("q", [0]) * (4 * n)
suffix = array("q", [0]) * (4 * n)
best = array("q", [0]) * (4 * n)
def pull(node):
left, right = node * 2, node * 2 + 1
total[node] = total[left] + total[right]
prefix[node] = max(prefix[left], total[left] + prefix[right])
suffix[node] = max(suffix[right], total[right] + suffix[left])
best[node] = max(best[left], best[right], suffix[left] + prefix[right])
def build(node, left, right):
if left == right:
total[node] = prefix[node] = suffix[node] = best[node] = values[left - 1]
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
pull(node)
def update(node, left, right, position, value):
if left == right:
total[node] = prefix[node] = suffix[node] = best[node] = value
return
middle = (left + right) // 2
if position <= middle:
update(node * 2, left, middle, position, value)
else:
update(node * 2 + 1, middle + 1, right, position, value)
pull(node)
def merge(a, b):
at, ap, ass, ab, al = a
bt, bp, bs, bb, bl = b
return (at + bt, max(ap, at + bp), max(bs, bt + ass),
max(ab, bb, ass + bp), al + bl)
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return total[node], prefix[node], suffix[node], best[node], right - left + 1
middle = (left + right) // 2
result = None
if query_left <= middle:
result = query(node * 2, left, middle, query_left, query_right)
if middle < query_right:
right_result = query(node * 2 + 1, middle + 1, right, query_left, query_right)
result = right_result if result is None else merge(result, right_result)
return result
build(1, 1, n)
answers = []
for _ in range(operations):
operation, x, y = map(int, input().split())
if operation == 1:
if x > y:
x, y = y, x
answers.append(str(query(1, 1, n, x, y)[3]))
else:
update(1, 1, n, x, y)
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-16 23:46
* update_at: 2026-07-16 23:46
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
建树 O(n)，每次修改或查询 O(log n)，空间 O(n)。
总结
最大子段和不是只存一个最大值；前缀和后缀正是跨越中点所需的边界信息。