1 问题
维护数组,支持把
区间赋值与 区间加法 使用同一套递归结构,但标记的含义不同。给每个数加
2 标记含义
完整覆盖节点
用 lazy[p] 记录赋值内容,另用 has[p] 记录是否存在尚未下传的赋值。
tr[p] = v * (r - l + 1);
lazy[p] = v;
has[p] = true;
先赋值
3 赋值为零
lazy[p] == 0 不能表示“没有标记”。把整段赋为零本身就是一次有效修改,后续访问孩子时,仍需把零传下去。
例如初始数组 lazy[p] == 0 跳过下传,再查询第一个元素就会错误地返回旧值
独立的 bool has[] 能区分“没有赋值”和“待下传的赋值恰好为零”,也无需选取某个数值作为哨兵。
4 下传与覆盖
部分修改或部分查询之前,若 has[p] 为真,就把 lazy[p] 分别赋给两个孩子,并覆盖孩子原有标记,最后清除父亲的 has[p]。
父亲的待下传赋值比孩子已有标记更新。若此前访问过孩子,递归规则本应已经先下传父亲的旧标记,因此可以放心让这次较新的赋值覆盖孩子。
完整覆盖时直接更新节点;部分覆盖时先下传、再递归,修改结束后上推。
查询先在不相交时返回
5 正确性
当递归进入节点时,祖先标记已经沿路径补齐。完整赋值把该节点的和直接改为
下传后,两个孩子都表示统一赋值后的区间;若它们原本有更旧的修改,也应被这次赋值覆盖。继续递归处理局部修改,再合并左右和,便得到正确结果。
6 代码
输入 n m、初始数组及 1 l r v 表示区间赋值,2 l r 表示求和。模板容量为 long long 范围内。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ls(int p) { return p << 1; } // 左孩子 2p
int rs(int p) { return p << 1 | 1; } // 右孩子 2p+1
const int maxn = 100000 + 5;
int n, m;
// tr[p] 保存区间和;lazy[p] 保存待下传的统一赋值。
ll a[maxn], tr[maxn * 4], lazy[maxn * 4];
bool has[maxn * 4]; // 赋值为 0 也有效,必须单独记录标记是否存在
// 部分修改结束后,用两个孩子重新求出父区间和。
void pushup(int p) {
tr[p] = tr[ls(p)] + tr[rs(p)];
}
// 建立表示 [l,r] 的节点 p,叶子取原数组值。
void build(int p, int l, int r) {
if (l == r) {
tr[p] = a[l];
return;
}
int mid = l + (r - l) / 2;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
pushup(p);
}
// 整段赋为 v:新赋值覆盖旧赋值,标记不能像加法那样累加。
void apply(int p, int l, int r, ll v) {
tr[p] = v * (r - l + 1);
lazy[p] = v;
has[p] = true;
}
// 需要进入孩子时,把较新的父赋值覆盖到两个孩子。
void pushdown(int p, int l, int r) {
if (!has[p]) return;
int mid = l + (r - l) / 2;
apply(ls(p), l, mid, lazy[p]);
apply(rs(p), mid + 1, r, lazy[p]);
has[p] = false; // 父标记已传完;lazy[p] 的旧内容不再有效
}
// 把目标区间 [L,R] 赋为 v;完整覆盖直接更新,否则先下传。
void assign_range(int p, int l, int r, int L, int R, ll v) {
if (L <= l && r <= R) {
apply(p, l, r, v);
return;
}
pushdown(p, l, r);
int mid = l + (r - l) / 2;
if (L <= mid) assign_range(ls(p), l, mid, L, R, v);
if (R > mid) assign_range(rs(p), mid + 1, r, L, R, v);
pushup(p);
}
// 先排除空交集,再判断完整覆盖;部分相交才下传并查询孩子。
ll query(int p, int l, int r, int L, int R) {
if (r < L || R < l) return 0; // 0 是求和的单位元
if (L <= l && r <= R) return tr[p];
pushdown(p, l, r);
int mid = l + (r - l) / 2;
return query(ls(p), l, mid, L, R)
+ query(rs(p), mid + 1, r, L, R);
}
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);
while (m--) {
int op;
cin >> op;
// 1 l r v:区间赋值;2 l r:区间求和。
if (op == 1) {
int l, r;
ll v;
cin >> l >> r >> v;
assign_range(1, 1, n, l, r, v);
} else {
int l, r;
cin >> l >> r;
cout << query(1, 1, n, l, r) << '\n';
}
}
return 0;
}
输入:
4 7
1 2 3 4
1 1 4 7
2 1 4
1 2 3 0
2 1 4
2 2 2
1 3 4 -2
2 2 4
输出:
28
14
0
-4
最后数组为
7 复杂度
建树
8 练习
- 在样例中增加一次“整段赋值为零,再查询中间单点”,跟踪
has的变化。 - 将查询改为区间最大值:整段赋值后最大值等于
,不再乘区间长度。 - 同时支持区间赋值和区间加,分别分析“先赋值后加”和“先加后赋值”的结果。
第三个问题需要考虑标记的复合顺序,在 多种懒标记 中继续讨论。
9 相关题解
暂无相关题解