区间赋值

1 问题

维护数组,支持把 [L,R][L,R] 的全部元素改为 vv,并查询区间和。

区间赋值与 区间加法 使用同一套递归结构,但标记的含义不同。给每个数加 vv,要保留旧值;把每个数赋为 vv,则应覆盖旧值。

2 标记含义

完整覆盖节点 [l,r][l,r] 时,新区间和为

sum⁡=v(r−l+1). \operatorname{sum}=v(r-l+1).

用 lazy[p] 记录赋值内容,另用 has[p] 记录是否存在尚未下传的赋值。

tr[p] = v * (r - l + 1);
lazy[p] = v;
has[p] = true;

先赋值 uu,再赋值 vv,最终结果只有 vv。因此新标记覆盖旧标记,不能累加。

整段赋值七之后,中间两项赋值零,最后只保留两端的七

3 赋值为零

lazy[p] == 0 不能表示“没有标记”。把整段赋为零本身就是一次有效修改,后续访问孩子时,仍需把零传下去。

例如初始数组 [1,2][1,2],整段赋值为 00 后,根的和已经是 00;若因 lazy[p] == 0 跳过下传,再查询第一个元素就会错误地返回旧值 11。

独立的 bool has[] 能区分“没有赋值”和“待下传的赋值恰好为零”,也无需选取某个数值作为哨兵。

4 下传与覆盖

部分修改或部分查询之前,若 has[p] 为真,就把 lazy[p] 分别赋给两个孩子,并覆盖孩子原有标记,最后清除父亲的 has[p]。

父亲的待下传赋值比孩子已有标记更新。若此前访问过孩子,递归规则本应已经先下传父亲的旧标记,因此可以放心让这次较新的赋值覆盖孩子。

完整覆盖时直接更新节点;部分覆盖时先下传、再递归,修改结束后上推。

查询先在不相交时返回 00,完整覆盖时返回节点和;只有部分相交时才下传,再递归两个孩子并将结果相加。孩子自行排除空交集,查询不需要上推。

5 正确性

当递归进入节点时,祖先标记已经沿路径补齐。完整赋值把该节点的和直接改为 vv 乘长度,记录的标记准确描述其孩子尚未执行的操作。

下传后,两个孩子都表示统一赋值后的区间;若它们原本有更旧的修改,也应被这次赋值覆盖。继续递归处理局部修改,再合并左右和,便得到正确结果。

6 代码

输入 n m、初始数组及 mm 次操作。1 l r v 表示区间赋值,2 l r 表示求和。模板容量为 n≤105n\le 10^5,所有和与赋值乘积需在 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,0,−2,−2][7,0,-2,-2]。

7 复杂度

建树 O(n)O(n),单次区间赋值或查询 O(log⁡n)O(\log n),空间 O(n)O(n)。标记将整段赋值压缩为一次常数时间操作。

8 练习

  1. 在样例中增加一次“整段赋值为零,再查询中间单点”,跟踪 has 的变化。
  2. 将查询改为区间最大值:整段赋值后最大值等于 vv,不再乘区间长度。
  3. 同时支持区间赋值和区间加,分别分析“先赋值后加”和“先加后赋值”的结果。

第三个问题需要考虑标记的复合顺序,在 多种懒标记 中继续讨论。

9 相关题解

暂无相关题解