用带懒标记的线段树维护区间和，支持区间加和区间查询。
OJ: luogu
题目 ID: P3372
难度:普及/提高-
标签:线段树懒标记区间加区间求和python
日期: 2026-07-16 23:59
题意
维护数列，支持区间加法和区间求和。
思路
节点保存覆盖区间的和。整段加 value 时，区间和增加 length * value，并把 value 记在懒标记中；只有在需要访问孩子时才下传。区间查询和修改都只访问对数个节点。
Python 知识
sys.stdin.buffer.readline减少大量操作的输入开销。- 用几个同长度列表保存线段树字段，比为每个节点创建对象更省内存。
if query_left <= middle和if middle < query_right只递归到真正相交的子树。
代码
python
import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
values = list(map(int, input().split()))
tree = [0] * (4 * n)
lazy = [0] * (4 * n)
def build(node, left, right):
if left == right:
tree[node] = values[left - 1]
return
middle = (left + right) // 2
build(node * 2, left, middle)
build(node * 2 + 1, middle + 1, right)
tree[node] = tree[node * 2] + tree[node * 2 + 1]
def apply(node, length, value):
tree[node] += length * value
lazy[node] += value
def push(node, left, right):
if lazy[node] and left != right:
middle = (left + right) // 2
apply(node * 2, middle - left + 1, lazy[node])
apply(node * 2 + 1, right - middle, lazy[node])
lazy[node] = 0
def update(node, left, right, query_left, query_right, value):
if query_left <= left and right <= query_right:
apply(node, right - left + 1, value)
return
push(node, left, right)
middle = (left + right) // 2
if query_left <= middle:
update(node * 2, left, middle, query_left, query_right, value)
if middle < query_right:
update(node * 2 + 1, middle + 1, right, query_left, query_right, value)
tree[node] = tree[node * 2] + tree[node * 2 + 1]
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return tree[node]
push(node, left, right)
middle = (left + right) // 2
answer = 0
if query_left <= middle:
answer += query(node * 2, left, middle, query_left, query_right)
if middle < query_right:
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] == 1:
update(1, 1, n, operation[1], operation[2], operation[3])
else:
answers.append(str(query(1, 1, n, operation[1], operation[2])))
print("\n".join(answers))原有 C++ 模板仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m;
long long a[MAXN];
long long tree_sum[MAXN * 4]; // tree_sum[p] 表示当前线段树节点覆盖区间的和。
long long lazy_add[MAXN * 4]; // lazy_add[p] 表示还没有下传给孩子的区间加标记。
void build(int p, int l, int r) {
if (l == r) {
tree_sum[p] = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
tree_sum[p] = tree_sum[p * 2] + tree_sum[p * 2 + 1];
}
void apply_add(int p, int l, int r, long long value) {
tree_sum[p] += value * (r - l + 1);
lazy_add[p] += value;
}
void push_down(int p, int l, int r) {
if (lazy_add[p] == 0 || l == r) {
return;
}
int mid = (l + r) / 2;
apply_add(p * 2, l, mid, lazy_add[p]);
apply_add(p * 2 + 1, mid + 1, r, lazy_add[p]);
lazy_add[p] = 0;
}
void range_add(int p, int l, int r, int ql, int qr, long long value) {
if (ql <= l && r <= qr) {
apply_add(p, l, r, value);
return;
}
push_down(p, l, r);
int mid = (l + r) / 2;
if (ql <= mid) {
range_add(p * 2, l, mid, ql, qr, value);
}
if (qr > mid) {
range_add(p * 2 + 1, mid + 1, r, ql, qr, value);
}
tree_sum[p] = tree_sum[p * 2] + tree_sum[p * 2 + 1];
}
long long query_sum(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree_sum[p];
}
push_down(p, l, r);
int mid = (l + r) / 2;
long long answer = 0;
if (ql <= mid) {
answer += query_sum(p * 2, l, mid, ql, qr);
}
if (qr > mid) {
answer += query_sum(p * 2 + 1, mid + 1, r, ql, qr);
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
long long k;
cin >> k;
range_add(1, 1, n, x, y, k);
} else {
cout << query_sum(1, 1, n, x, y) << '\n';
}
}
return 0;
}复杂度
建树 O(n)，每次操作 O(log n)，空间 O(n)。
总结
懒标记就是“先在大区间记账，访问子区间时再摊开”。
