无聊的数列

形式化题目

有一个长度为 $n$ 的整数数列 $a$ ，初始值给定。给出 $m$ 次操作：

对区间 $[l,r]$ 内的每个位置 $i$ 加上 $K + (i-l) \cdot D$ （一个首项 $K$ 、公差 $D$ 的等差数列）；
询问位置 $p$ 的当前值 $a_p$ 。

要求按顺序处理全部操作并输出每次询问的答案。

暴力

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * 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-08-12 22:03
 * update_at: 2026-08-12 22:03
 */
// brute.cpp：小数据暴力解，直接按题意逐项加等差数列，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n, m;
long long a[MAXN]; // a[i] 表示当前位置的当前值

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    while (m--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int l, r;
            long long K, D;
            cin >> l >> r >> K >> D;
            // 区间加等差数列：暴力逐项加。
            for (int i = l; i <= r; i++) {
                a[i] += K + (i - l) * D;
            }
        } else {
            int p;
            cin >> p;
            cout << a[p] << '\n';
        }
    }

    return 0;
}

brute.cpp 直接维护数组：操作 1 逐项加等差数列，操作 2 输出当前位置，单次操作 $O(n)$ ，总复杂度 $O(nm)$ ，无法通过 $10^5$ 的数据。下面两种解法都以它为对拍基准。

思路

本题有两种 $O(\log n)$ 的经典做法，正式主解是解法一（双树状数组），对应 main.cpp：

解法一：把等差数列拆成"常数系数 + 下标系数"，两个差分数组退化成四次端点修改，前缀和由两个 Fenwick 维护——代码最简单、常数最小。
解法二：直接在线段树上打"等差数列"懒标记，整段命中的节点 $O(1)$ 结算区间和——概念更通用，可扩展成区间查询。

解法一：双树状数组（差分）

思路

关键观察是拆系数：第 $i$ 项的增量

K + (i-l) \cdot D = (K - l \cdot D) + i \cdot D

是一个"常数部分 $(K - lD)$ “与"下标系数部分 $D$ "之和，而且两部分在 $[l,r]$ 上都是均匀加的常数。于是区间加等差数列退化成两个"区间加常数”，而区间加常数在差分数组上只需改两个端点；最后单点值用差分前缀和恢复，前缀和正好由树状数组维护。

用两个 Fenwick：c_diff 维护常数系数的差分，x_diff 维护下标系数的差分。操作 1 只做四次端点单点加；操作 2 输出 $a_p = a_0[p] + \text{prefix\_sum}(c\_diff, p) + p \cdot \text{prefix\_sum}(x\_diff, p)$ 。

数学视角：为什么差分 + 树状数组可行

查询信息构成幺半群：单点值由差分前缀和恢复，前缀和用 $+$ 合并，构成交换幺半群 $(\mathbb{Z}, +, 0)$ 。
区间加常数是摘要上的自同态：差分数组的单点加 $v$ 等价于"所有位置 $\geqslant pos$ 的前缀和同时加 $v$ "： $\text{add}_v(\text{prefix}(p)) = \text{prefix}(p) + v \ (p \geqslant pos)$ ，且多个加法可合并成一个和。这就是树状数组可以把修改压缩到 $\log n$ 个节点、查询沿 lowbit 累加的原因。

以样例为例，操作 1 2 4 1 2（ $K=1, D=2, l=2$ ）拆开后各位置的增量如下：

位置 $i$	2	3	4
常数系数 $K - lD = -3$	-3	-3	-3
下标系数 $i \cdot D$	4	6	8
增量合计	1	3	5
修改后 $a_i$	3	6	9

观察表中"增量合计"一行：它正是 $K + (i-l)D$ 在 $i = 2,3,4$ 的值（ $1,3,5$ ）。常数行和下标系数行各自在区间内是常数，所以差分数组上各只需 $l$ 、 $r+1$ 两个端点；查询位置 $3$ 时，常数前缀和为 $-3$ 、下标系数前缀和为 $2$ ， $a_3 = 3 + (-3) + 3 \times 2 = 6$ ，与样例输出一致。

代码

cpp

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/**
 * 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-08-12 22:03
 * update_at: 2026-08-12 22:03
 */
#include <bits/stdc++.h>
using namespace std;

// 仿照 rbook 模板 fenwick：单点加、前缀和，下标从 1 开始。
template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    static int lowbit(int x) {
        return x & -x;
    }

    // 给差分数组的一个位置增加 value。
    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    // 求差分数组 [1, pos] 的前缀和。
    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }
};

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];
    }

    Fenwick<long long> c_diff(n); // 常数系数 (K - l*D) 的差分数组
    Fenwick<long long> x_diff(n); // 下标系数 D 的差分数组

    while (m--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int l, r;
            long long K, D;
            cin >> l >> r >> K >> D;
            // 第 i 项增加 (K - l*D) + i*D，两个系数都在 [l,r] 上加常数，
            // 于是差分数组只需在 l 处加、r+1 处减。
            long long c = K - l * D;
            c_diff.add(l, c);
            c_diff.add(r + 1, -c);
            x_diff.add(l, D);
            x_diff.add(r + 1, -D);
        } else {
            int p;
            cin >> p;
            // a[p] = 初始值 + 常数系数前缀和 + p * 下标系数前缀和。
            long long ans = a[p] + c_diff.prefix_sum(p) + p * x_diff.prefix_sum(p);
            cout << ans << '\n';
        }
    }

    return 0;
}

复杂度

时间：单次操作 $O(\log n)$ ，总 $O((n+m) \log n)$ 。
空间：两个 Fenwick 加初始数组， $O(n)$ 。

解法二：线段树（等差数列懒标记）

思路

线段树不拆系数，直接把"待加的等差数列"作为懒标记：节点除了存区间和 sum，还存两个懒标记 first（该区间最左端位置待加的值）与 diff（公差）。整段命中时 $O(1)$ 结算：

\text{sum}' = \text{sum} + \text{len} \cdot f + d \cdot \frac{\text{len}(\text{len}-1)}{2}

下传时右儿子的首项要平移：左端从 $l$ 变成 $\text{mid}+1$ ，首项增加 $(\text{mid}+1-l) \cdot d$ 。单点查询沿根到叶子下传所有懒标记后，叶子节点的 sum 就是当前位置的当前值。

与解法一对比：解法二不需要拆系数公式，任何"等差数列区间加"都能直接打标记（包括区间加普通常数 $D=0$ 的特例），并且天然支持区间求和；代价是每个节点多两个 long long 懒标记，常数比双 Fenwick 略大。

代码

cpp

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129/**
 * 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-08-13 08:46
 * update_at: 2026-08-13 08:46
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

ll a[MAXN]; // 初始数列

// 仿照 rbook 模板 segtree-range-assign 的 pull/apply/push 结构，
// 懒标记从「区间赋值」改成「待加等差数列」。
struct SegmentTreeAP {
    int n = 0;
    vector<ll> sum;   // sum[p]：节点 p 区间的和
    vector<ll> first; // 懒标记：该区间最左端位置待加的值
    vector<ll> diff;  // 懒标记：该区间待加的公差

    SegmentTreeAP(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        sum.assign(n * 4 + 5, 0);
        first.assign(n * 4 + 5, 0);
        diff.assign(n * 4 + 5, 0);
    }

    void pull(int p) {
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }

    // 节点 p 的整段区间 [l, r] 加上首项 f、公差 d 的等差数列。
    // 区间和增加 len*f + d*len*(len-1)/2（首项到末项求和）。
    void apply(int p, int l, int r, ll f, ll d) {
        ll len = r - l + 1;
        sum[p] += len * f + d * len * (len - 1) / 2;
        first[p] += f;
        diff[p] += d;
    }

    // 把节点 p 的懒标记下传给两个儿子。
    void push(int p, int l, int r) {
        if (first[p] == 0 && diff[p] == 0)
            return;
        int mid = (l + r) >> 1;
        apply(p << 1, l, mid, first[p], diff[p]);
        // 右儿子左端位置是 mid+1，首项要平移 (mid + 1 - l) * diff。
        apply(p << 1 | 1, mid + 1, r, first[p] + (mid + 1 - l) * diff[p], diff[p]);
        first[p] = 0;
        diff[p] = 0;
    }

    void build(int l, int r, int p = 1) {
        if (l == r) {
            sum[p] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, p << 1);
        build(mid + 1, r, p << 1 | 1);
        pull(p);
    }

    // 区间 [ql, qr] 加上首项 K、公差 D 的等差数列：
    // 位置 i 增加 K + (i - ql) * D。
    void add_ap(int ql, int qr, ll K, ll D, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply(p, l, r, K + (l - ql) * D, D);
            return;
        }
        push(p, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid)
            add_ap(ql, qr, K, D, l, mid, p << 1);
        if (qr > mid)
            add_ap(ql, qr, K, D, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    // 单点查询位置 pos 的当前值。
    ll query(int pos, int l, int r, int p = 1) {
        if (l == r)
            return sum[p];
        push(p, l, r);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return query(pos, l, mid, p << 1);
        return query(pos, mid + 1, r, p << 1 | 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    SegmentTreeAP seg(n);
    seg.build(1, n);

    while (m--) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int l, r;
            ll K, D;
            cin >> l >> r >> K >> D;
            seg.add_ap(l, r, K, D, 1, n);
        } else {
            int p;
            cin >> p;
            cout << seg.query(p, 1, n) << '\n';
        }
    }

    return 0;
}

复杂度

时间：单次操作 $O(\log n)$ ，总 $O((n+m) \log n)$ 。
空间：线段树四倍数组（sum/first/diff 各 $4n$ ）， $O(n)$ 。

复杂度对比

方案	单次操作	空间	常数	扩展性
解法一双 Fenwick	$O(\log n)$	$O(n)$	小	只能单点查询；需拆系数
解法二线段树	$O(\log n)$	$O(n)$ （约 $12n$ 字节）	略大	支持区间查询；不需拆系数

两者时间渐近相同。只做单点查询时解法一更省；需要区间求和、或懒得拆系数时，解法二更通用。

总结

"等差数列区间加"有两条经典路线：拆成"常数 + 下标 $\times$ 系数"退化出两个区间加常数（差分 + 双 Fenwick），或者把等差数列整体作为懒标记（线段树）。前者代码短、常数小，后者通用、可扩展区间查询。rbook 的《树状数组：单点修改与区间查询》（模板 fenwick）与《线段树：区间赋值与区间查询》（模板 segtree-range-assign，本解 pull/apply/push 结构即由其改造）分别对应两种解法。

图示解析

这张 ASCII 图展示两种解法的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15朴素模拟（brute.cpp）
  对 [l,r] 逐项加 K + (i-l)*D          O(n) 每次操作
        |
        | 瓶颈：逐项访问区间，m 次操作 O(n*m) 太大
        v
解法一（main.cpp，正式主解）           解法二（main-segtree.cpp）
拆系数                                 等差数列懒标记
K + (i-l)*D = (K - l*D) + i*D         节点存 first/diff 两个懒标记
两个区间加常数 -> 差分端点 l/r+1       整段命中: sum += len*f + d*len(len-1)/2
双 Fenwick 维护前缀和                  下传时右儿子首项平移 (mid+1-l)*d
查询: a0[p] + prefix_c(p) + p*prefix_x  单点查询沿路径下传后取叶子 sum
        |                               |
        +----------+--------------------+
                   v
复杂度 O((n + m) log n)，空间 O(n)

图中上方分叉是两种优化路线的分水岭：解法一在"增量"上做代数变形，解法二在"数据结构"上扩展懒标记。共同点都是把"区间内每个位置增量不同"的困难压缩成 $O(\log n)$ 个节点的整段结算。

目录