无聊的数列

题意

给 [l,r] 加上首项为 K、公差为 D 的等差数列，并查询某个位置的值。

思路

第 i 项增加 K + (i-l)D = (K-lD) + iD。因此只要分别维护“常数项系数”和“位置系数”的差分数组即可：在 [l,r] 的差分端点加上这两个系数，单点查询时取两个 Fenwick 前缀和。

Python 知识

array("q") 保存整数差分，避免 Python 对象列表的额外空间。
iter(map(int, read().split())) 让所有整数共享一次解析流程。
生成器表达式 (next(data) for _ in range(4)) 适合读取变长操作。

代码

python

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
43import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
n, operations = next(data), next(data)
values = [next(data) for _ in range(n)]
constant = array("q", [0]) * (n + 2)
linear = array("q", [0]) * (n + 2)


def add(tree, index, value):
    while index <= n:
        tree[index] += value
        index += index & -index


def prefix(tree, index):
    result = 0
    while index:
        result += tree[index]
        index -= index & -index
    return result


def range_add(tree, left, right, value):
    add(tree, left, value)
    if right < n:
        add(tree, right + 1, -value)


answers = []
for _ in range(operations):
    operation = next(data)
    if operation == 1:
        left, right, first, difference = (next(data) for _ in range(4))
        range_add(constant, left, right, first - left * difference)
        range_add(linear, left, right, difference)
    else:
        position = next(data)
        answers.append(str(values[position - 1] + prefix(constant, position)
                          + position * prefix(linear, position)))
print("\n".join(answers))

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-16 23:46
 * update_at: 2026-07-16 23:46
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

每次修改和查询均为 O(log n)，空间 O(n)。

总结

等差数列看似需要修改很多位置，拆成“常数项 + 下标系数”后仍然只是两个差分端点。

目录

题意

思路

Python 知识

代码

复杂度

总结