在线段树中同时维护区间赋值、区间加法和区间最大值。
OJ: luogu
题目 ID: P1253
难度:普及+/提高
标签:线段树懒标记区间赋值区间最大值python
日期: 2026-07-16 23:59
题意
支持把区间全部赋为 x、把区间全部加上 x，以及查询区间最大值。
思路
节点保存最大值，并维护两个标记：未下传的赋值 assigned 和追加加法 addition。赋值会覆盖旧的加法；加法若遇到已有赋值就直接改写赋值，否则累加到 addition。下传时先赋值、后加法。
Python 知识
bytearray保存“是否存在赋值标记”，因为赋值本身可能是负数，不能用数值正负判断。array("q")紧凑保存最多四百万个 64 位线段树字段，控制百万规模数据的内存。(set_value if operation == 1 else add_value)(...)用函数对象选择两种更新。- 查询初值取很小的负数，能够正确处理全负数区间。
代码
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", map(int, input().split()))
maximum = array("q", [0]) * (4 * n)
addition = array("q", [0]) * (4 * n)
assigned = array("q", [0]) * (4 * n)
has_assignment = bytearray(4 * n)
def build(node, left, right):
if left == right:
maximum[node] = values[left - 1]
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
maximum[node] = max(maximum[node * 2], maximum[node * 2 + 1])
def set_value(node, value):
maximum[node] = assigned[node] = value
addition[node] = 0
has_assignment[node] = 1
def add_value(node, value):
maximum[node] += value
if has_assignment[node]:
assigned[node] += value
else:
addition[node] += value
def push(node, left, right):
if left == right:
return
child_left, child_right = node * 2, node * 2 + 1
middle = (left + right) // 2
if has_assignment[node]:
set_value(child_left, assigned[node])
set_value(child_right, assigned[node])
has_assignment[node] = 0
if addition[node]:
add_value(child_left, addition[node])
add_value(child_right, addition[node])
addition[node] = 0
def update(node, left, right, query_left, query_right, operation, value):
if query_left <= left and right <= query_right:
(set_value if operation == 1 else add_value)(node, value)
return
push(node, left, right)
middle = (left + right) // 2
if query_left <= middle:
update(node * 2, left, middle, query_left, query_right, operation, value)
if middle < query_right:
update(node * 2 + 1, middle + 1, right, query_left, query_right, operation, value)
maximum[node] = max(maximum[node * 2], maximum[node * 2 + 1])
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return maximum[node]
push(node, left, right)
middle = (left + right) // 2
answer = -10**30
if query_left <= middle:
answer = max(answer, query(node * 2, left, middle, query_left, query_right))
if middle < query_right:
answer = max(answer, query(node * 2 + 1, middle + 1, right, query_left, query_right))
return answer
build(1, 1, n)
answers = []
for _ in range(operations):
operation = list(map(int, input().split()))
if operation[0] == 3:
answers.append(str(query(1, 1, n, operation[1], operation[2])))
else:
update(1, 1, n, operation[1], operation[2], operation[0], operation[3])
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)。
总结
多个懒标记共存时，先写清楚“新操作作用在旧标记之后”的复合顺序，代码就不会混乱。