区间修改并不总能压成一个懒标记。对每个元素取模时，区间和本身不足以告诉我们新的区间和；但如果这一段的最大值小于模数，整段就完全不用修改。

这篇接在线段树三题与子树染色之后，换一个问题：无法整段更新时，能否证明真正发生变化的次数足够少？438D 的关键不是让每次取模都变成 O(log n)，而是让整串操作的总成本有上界。

阅读前

会维护区间和

理解建树、单点赋值和父节点合并即可，不需要预先掌握 Segment Tree Beats。

关键问题

哪些节点不用访问

最大值判定无变化；减半性质限制真正修改叶子的次数。

完成标志

解释单次与总成本

既能构造一次 O(n) 的更新，也能证明多次更新的均摊界。

官方题目与操作范围

题目为 Codeforces 438D The Child and Sequence。以下范围、难度与标签于 2026-10-05 根据官方题目页核对，解释为本站原创。

项目 官方信息
难度与标签 2300；data structures、math
数组长度 n、操作数 m 均为 1 到 100000
初始元素、赋值 x、模数 x 均为 1 到 1000000000
1 l r 查询闭区间内元素之和
2 l r x 对区间内每个元素分别取模 x
3 k x 把第 k 个元素赋值为 x

初始值和赋值是正数，但取模后可以出现 0。区间和最高达到 10^14，需要 long long；不能把“单个值放得下 int”当作和也放得下的理由。

为什么区间和不能直接打取模标记

朴素数组逐项取模，单次最坏 O(n)，m 次最坏 O(nm)。先尝试普通区间和线段树：能否把 sum %= x 作为更新？不能。例如 [5,5] 对 4 取模后和为 2，而原和 10 % 4 也为 2 只是巧合；换成 [6,4]，原和仍为 10，新和却为 2；再换 [7,3]，新和变成 6。

原数组 原和 原和对 4 取模 逐项取模后的和
[5,5] 10 2 2
[6,4] 10 2 2
[7,3] 10 2 6

即使额外维护最大值，也不够直接算新和。比较 [7,5,4] 与 [7,6,3]：它们的和都为 16、最大值都为 7，对 4 取模后的和分别为 4 与 8。因此 sum 和 max 不能代表取模所需的完整分布。最大值在这里负责的是判定何时不必修改，而不是算出整段修改结果。

节点只存和与最大值

对节点区间 [L,R] 定义 sum 为所有元素之和，mx 为最大值。两个孩子合并时，和相加、最大值取较大者。查询和、单点赋值与普通线段树相同。

取模更新按以下顺序处理：区间不相交就返回；若 mx < x，说明每个非负元素都小于 x，取模不改变任何值，也返回；否则，叶子直接做 % x，内部节点访问两个孩子并重新合并。

mx == x 不能剪掉：等于 x 的元素必须变成 0。这个实现没有取模懒标记，不需要下传；所有数值变化都落实到叶子，父节点随回溯更新。

正确性从叶子向上证明

建树后，叶子的和与最大值等于元素，内部节点由合并规则满足定义。单点赋值直接改叶子，沿路径重新合并，因此保持不变量。

对一次取模更新按节点长度归纳。不相交节点不该改变；mx < x 时，全区间都不会改变，剪枝正确。剩下的叶子与目标区间相交，执行精确的 % x。内部节点分别正确更新孩子，再合并正确的和与最大值，所以整个更新正确。查询把目标区间拆成互不相交的节点，返回各段和，相加得到答案。

注意：剪枝条件对部分相交节点也成立。若整个节点都小于 x，它在目标区间内的那部分当然也小于 x。

手算一次修改再一次重置

以下为原创小例子：初始数组 [7,5,4,3]。

操作 操作后的数组 查询输出或观察
1 1 4 [7,5,4,3] 19
2 1 4 4 [3,1,0,3] 原最大值不小于 4，需向下访问
1 1 4 [3,1,0,3] 7
2 2 4 4 [3,1,0,3] 最大值小于 4，相关节点可剪掉
3 3 9 [3,1,9,3] 单点赋值重新抬高局部最大值
2 2 3 5 [3,1,4,3] 第二项不变，第三项减小
1 2 3 [3,1,4,3] 5

第二次取模不需要为所有元素重复计算。单点赋值则提醒我们：数值不是永远只减不增，复杂度证明必须把“重新抬高”算进去。

一次有效取模为什么至少减半

设当前值为 a，模数为 x，且取模确实改变了值。由于 a 非负、x 正，因此 a≥x。分两种情况：

模数位置 新值的界
x≤a/2 a % x < x ≤ a/2
x>a/2 a 只含一个 x，a % x = a-x < a/2

无论哪种情况，新值都严格小于 a/2。这不是“通常下降得快”，而是每次有效取模都满足的数值界。

可以取势能 Phi = Σ ceil(log2(a[i]+1))。有效取模使对应项至少下降 1；0 的势能为 0。初始势能 O(n log(A+1))，每次单点赋值最多补入 O(log(A+1))，其中 A 是初始值与所有赋值的最大值。于是有效叶子修改总数 K 为 O((n+s)log(A+1))，s 是单点赋值次数。

单次最坏与均摊界必须分开

一次更新可以修改所有元素：把 n 个 10^9 都对 1 取模，就要访问整棵树，成本 O(n)。所以不能宣称区间取模单次 O(log n)。

若一次更新真正修改 k 个叶子，除边界路径外，每个未剪枝的相交内部节点都通往至少一个发生变化的叶子。把这些路径及其常数个被剪枝兄弟计入，访问数为 O((k+1)log n) 的上界。整个操作序列的成本因此为：

O(n + (m + (n+s)log(A+1))log n)，空间 O(n)。

这里用的是非紧的安全上界；实际共享路径可以减少访问。查询与赋值各为 O(log n)，建树 O(n)。若没有最大值剪枝，仍会反复扫过已经不变的元素，减半性质就无法转化为程序的总成本保证。

自测 为什么不能把取模当作普通懒标记

先用两个和相同、最大值相同的数组试算。再问自己：节点摘要能算出新和吗，还是只能保证本段完全不变？

本文的职责划分是：sum 回答查询，mx 识别无效修改，叶子执行真正取模。均摊分析证明向下走的总次数，而非替代更新逻辑。

完整 C++17 实现

下标从 1 开始，所有区间使用闭区间。代码仅使用 C++17 标准库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

class SegmentTree {
    int n;
    vector<long long> sum, mx;

    void pull(int p) {
        sum[p] = sum[p * 2] + sum[p * 2 + 1];
        mx[p] = max(mx[p * 2], mx[p * 2 + 1]);
    }
    void build(int p, int l, int r, const vector<long long>& a) {
        if (l == r) {
            sum[p] = mx[p] = a[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(p * 2, l, mid, a);
        build(p * 2 + 1, mid + 1, r, a);
        pull(p);
    }
    long long query(int p, int l, int r, int ql, int qr) const {
        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return sum[p];
        int mid = l + (r - l) / 2;
        return query(p * 2, l, mid, ql, qr)
             + query(p * 2 + 1, mid + 1, r, ql, qr);
    }
    void modulo(int p, int l, int r, int ql, int qr, long long x) {
        if (r < ql || qr < l || mx[p] < x) return;
        if (l == r) {
            sum[p] %= x;
            mx[p] = sum[p];
            return;
        }
        int mid = l + (r - l) / 2;
        modulo(p * 2, l, mid, ql, qr, x);
        modulo(p * 2 + 1, mid + 1, r, ql, qr, x);
        pull(p);
    }
    void assign(int p, int l, int r, int k, long long x) {
        if (l == r) {
            sum[p] = mx[p] = x;
            return;
        }
        int mid = l + (r - l) / 2;
        if (k <= mid) assign(p * 2, l, mid, k, x);
        else assign(p * 2 + 1, mid + 1, r, k, x);
        pull(p);
    }
public:
    explicit SegmentTree(const vector<long long>& a)
        : n(static_cast<int>(a.size()) - 1),
          sum(4 * n + 4), mx(4 * n + 4) {
        build(1, 1, n, a);
    }
    long long query(int l, int r) const { return query(1, 1, n, l, r); }
    void modulo(int l, int r, long long x) { modulo(1, 1, n, l, r, x); }
    void assign(int k, long long x) { assign(1, 1, n, k, x); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    SegmentTree tree(a);
    while (m--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            cout << tree.query(l, r) << '\n';
        } else if (type == 2) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            tree.modulo(l, r, x);
        } else {
            int k;
            long long x;
            cin >> k >> x;
            tree.assign(k, x);
        }
    }
}

边界与错误清单

边界或错误 检查方法
最大值等于 x 不可用 mx <= x 剪枝
x=1 所有目标元素变成 0
已经全为 0 合法状态，以 mx < x 返回
n=1、l=r 单叶更新与查询照常成立
取模之后再赋大值 赋值路径必须同时更新最大值
只更新 sum 不更新 mx 剪枝会失真，甚至错误跳过更新
多次不相交区间 先检查范围，不误改邻居
和超过 32 位 10^5 个 10^9 的和为 10^14
忽略单点赋值的势能补充 会错误声称整个过程中每个位置只能变 O(log A) 次

独立对拍使用直接数组，不复用线段树剪枝或势能模型。大规模验证应同时包含全区间清零、反复无效取模、单点重新抬高和 64 位区间和。

与已有线段树问题比较

文章 修改如何处理 证明重点
52C 区间加 标记可整段合成 摘要更新与下传一致
620E 子树染色 覆盖位集，后标记替换前标记 集合并集与覆盖顺序
本题区间取模 无变化剪枝，其余到叶子 有效修改减半与势能补充

看见区间修改时，先尝试摘要能否整体变换；若不能，再寻找“何时不变”和“变化多少次”。本题属于值域收缩驱动的均摊线段树，并不等于已经实现了通用的 Segment Tree Beats。