线段树二分 2

形式化题目

有一个长度为 $n$ 的整数数列 $a_1, a_2, \dots, a_n$ , 初始值给定. 需要按顺序处理 $m$ 次操作:

区间加: 给出 $x, y, k$ , 把 $a_x, a_{x+1}, \dots, a_y$ 每个数都加上 $k$ .
区间和: 给出 $x, y$ , 求 $\sum_{i=x}^{y} a_i$ .
区间查找: 给出 $x, y, d$ , 记 $S_i = \sum_{j=x}^{i} a_j$ . 求最小的 $i \in [x, y]$ 使 $S_i \geqslant d$ ; 若 $[x, y]$ 内所有 $S_i < d$ , 输出 $y+1$ .
单点赋值: 给出 $x, d$ , 令 $a_x = d$ .

暴力解法

思路

按定义直接做: 用一个数组存数列. 操作 1 逐项加, 操作 2 逐项累加, 操作 4 直接改一个位置. 操作 3 从 $x$ 开始往右累加 $S_i$ , 遇到第一个 $S_i \geqslant d$ 就输出 $i$ , 走完整个区间都没有就输出 $y+1$ .

这段代码的价值有两个: 它把操作 3 的语义写死成一个可以直接对照的定义, 后面所有优化都必须和它的输出逐字节相同; 对拍时也用它当基准.

代码

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/**
 * 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-10-27 15:41
 * update_at: 2026-10-27 15:41
 */
// brute.cpp：小数据暴力解，直接维护数列，每个操作逐元素模拟。
// 用来讲清操作 3 的含义（第一个让 a[x] + ... + a[i] >= d 的 i），并和 main.cpp 对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000000 + 5;

int n, m;
ll a[MAXN];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    for (int step = 1; step <= m; step++) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int x, y;
            ll v;
            scanf("%d %d %lld", &x, &y, &v);
            for (int i = x; i <= y; i++) a[i] += v;
        } else if (op == 2) {
            int x, y;
            scanf("%d %d", &x, &y);
            ll answer = 0;
            for (int i = x; i <= y; i++) answer += a[i];
            printf("%lld\n", answer);
        } else if (op == 3) {
            int x, y;
            ll d;
            scanf("%d %d %lld", &x, &y, &d);
            ll acc = 0;          // acc = a[x] + ... + a[i]
            int answer = y + 1;  // 整段都不到 d 时按要求输出 y + 1
            for (int i = x; i <= y; i++) {
                acc += a[i];
                if (acc >= d) {
                    answer = i;
                    break;
                }
            }
            printf("%d\n", answer);
        } else {
            int x;
            ll d;
            scanf("%d %lld", &x, &d);
            a[x] = d;
        }
    }
    return 0;
}

复杂度

时间: 除操作 4 外每次操作 $O(n)$ , 总 $O(nm)$ . 当 $n, m$ 都到 $10^6$ 时是 $10^{12}$ 量级的基本操作.
空间: $O(n)$ .

瓶颈

瓶颈有两处, 分别对应正解的两步:

操作 1、2 每次都真的去碰一整段区间, 但一次区间操作真正改动到的信息, 可以归结到 $O(\log n)$ 个线段树结点各自的"段和"上. 把这 $O(\log n)$ 个段和挂到树上, 一次区间操作就只要 $O(\log n)$ 步.
操作 3 是一次"在区间里找第一个达标位置"的查找, 暴力每次都要从头扫. 线段树上的每个结点天然带着"这一整段的和", 于是一整段能不能达标可以一次判断完, 查找变成沿着树走一条路径.

正解

思路

第一步是把操作 1、2、4 换成懒标记线段树. 每个结点记录两样东西: 这一段元素的和 sum, 以及"整段都要加、但还没加到儿子上"的标记 tag.

区间加: 当前结点被 $[x, y]$ 完全覆盖时, 直接把 tag 加上 $k$ , 并让 sum 增加 $k \times$ 段长, 不再往下走; 否则先把 tag 推给两个儿子, 再递归到相交的儿子, 回来后用两个儿子的和重算自己.
区间和: 完全覆盖就直接返回 sum; 否则下推标记后递归, 把相交儿子的答案相加.
单点赋值: 沿路下推标记, 走到叶子后把 sum 写成 $d$ 并把 tag 清 $0$ , 回来一路上推. 先下推是必须的, 否则叶子会被祖先的旧标记二次影响.

第二步是操作 3. 判断条件 $\sum_{j=x}^{i} a_j \geqslant d$ 不好直接用, 改成跟踪"还差多少": 记 need 初始等于 $d$ , 含义是"当前前缀和距离 $d$ 还差这么多". 然后在树上按从左到右的顺序处理 $[x, y]$ 的各个结点:

结点被 $[x, y]$ 完全覆盖, 且 sum < need: 这一整段的所有元素加起来都不够, 段内任何位置都达不到 $d$ . 于是整段丢掉, 同时把 need 减去 sum, 表示这段的前缀和已经吃掉了这么多.
结点被 $[x, y]$ 完全覆盖, 且 sum >= need: 答案一定落在这一段里. 先下推标记, 再先看左儿子, 左儿子里找不到才看右儿子.
结点只被 $[x, y]$ 部分覆盖: 下推标记后, 递归到与 $[x, y]$ 相交的儿子, 仍然先左后右.

走到叶子时返回它的下标. 若处理完整个 $[x, y]$ 都没返回, 说明区间内每个位置都 $< d$ , 输出 $y+1$ . 区间只剩一个位置( $x = y$ )时, 整段就是一片叶子, 判断一次就结束.

一次询问访问的结点可以分成三部分: 两条边界路径上被部分覆盖的结点, 一共 $O(\log n)$ 个; 被整段跳过或整段命中的规范结点, 每层至多常数个, 一共 $O(\log n)$ 个; 以及命中之后答案段内往下的一条路径, $O(\log n)$ 个. 三部分相加仍是 $O(\log n)$ , 不存在"每层都要扫一遍整层"的情况.

为什么要求元素非负

上面"整段和 $<$ 还差多少, 就整段跳过"这一步, 依赖的是段内前缀和不减: 只有不减, 才能由"段内最大值(也就是段尾的前缀和)都不到 need"推出段内没有任何位置达标.

元素可能为负时这个推理是假的. 取 $a = [10, -100, 20]$ , 询问 $[1, 3]$ 且 $d = 5$ :

真正的答案: $S_1 = 10 \geqslant 5$ , 所以答案是 $1$ .
按"整段和不够就跳过": 整段和是 $-70 < 5$ , 会跳过整段, 错误地输出 $4$ .

也就是说, 有负数时必须维护区间最大前缀和才能判断"这一段里有没有位置达标". 但区间加和最大前缀和是不兼容的: 整段加 $v$ 时, 第 $i$ 个前缀增加的是 $i \cdot v$ , 不是统一加 $v$ . 例如 $[-1, 2, -10, 7, 3]$ 整段加 $9$ 后最大前缀和从 $1$ 变成 $46$ , 没法用"最大值 $+9$ "算出来.

本题题面把操作 3 描述成"在前缀和数组上做 lower_bound", 这个说法本身就要求前缀和单调不减, 即所有元素非负; 题面里操作 4 的赋值与初始值也都是正整数. 所以下面的实现按元素非负来写.

样例上的执行过程

样例在操作 3 之前已经把数列变成了 $a = [2, 8, 7, 3, 4]$ , 询问是 3 1 5 6, 即 $d = 6$ . 线段树按 $[1,5] \to [1,3] + [4,5] \to [1,2] + [3,3]$ 拆分, 各段和如图:

text

1
2
3
4
5
6
7
8
9[1,5] sum=24
├─ [1,3] sum=17
│  ├─ [1,2] sum=10
│  │  ├─ [1,1] sum=2
│  │  └─ [2,2] sum=8
│  └─ [3,3] sum=7
└─ [4,5] sum=7
   ├─ [4,4] sum=3
   └─ [5,5] sum=4

从根开始, need = 6:

访问顺序	结点区间	区间和	与 `need` 比较	处理
1	$[1,5]$	24	$24 \geqslant 6$	答案在里面, 往左儿子走
2	$[1,3]$	17	$17 \geqslant 6$	往左儿子走
3	$[1,2]$	10	$10 \geqslant 6$	往左儿子走
4	$[1,1]$	2	$2 < 6$	整段丢掉, `need` 变成 $4$
5	$[2,2]$	8	$8 \geqslant 4$	叶子, 答案是 $2$

整棵树只走了 $[1,5] \to [1,3] \to [1,2] \to [1,1] \to [2,2]$ 这一条路, $[3,3]$ 和 $[4,5]$ 连访问都没有. 把第 4 行和暴力对照: 暴力在这一步也是把 $a_1 = 2$ 加进前缀和后发现还差 $4$ , 两者算的是同一件事, 只是一个一个走、一个按段跳.

代码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185/**
 * 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-10-27 15:48
 * update_at: 2026-10-27 15:48
 */
// U420425 线段树二分 2：区间加、区间和、单点赋值，以及区间内第一个让前缀和达到 d 的位置。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000000 + 5;
const int MAXNODE = MAXN * 4;

int n, m;
ll a[MAXN];

// node[p].sum：结点 p 覆盖区间的元素和
// node[p].tag：结点 p 上待下传的加法标记（还没加到两个儿子上）
struct Node {
    ll sum;
    ll tag;
};
Node node[MAXNODE];

// 快速读入：本题最多 5e6 个整数，cin 在 1s 时限下不够用
const int BUFSIZE = 1 << 16;
char buf[BUFSIZE];
int buf_len = 0;
int buf_pos = 0;

inline char read_char() {
    if (buf_pos == buf_len) {
        buf_len = fread(buf, 1, BUFSIZE, stdin);
        buf_pos = 0;
        if (buf_len <= 0) return 0;
    }
    return buf[buf_pos++];
}

inline ll read_int() {
    char c = read_char();
    while (c != 0 && c != '-' && (c < '0' || c > '9')) c = read_char();
    int sign = 1;
    if (c == '-') {
        sign = -1;
        c = read_char();
    }
    ll x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = read_char();
    }
    return x * sign;
}

// 上推：父结点的区间和 = 两个儿子的区间和之和
void push_up(int p) {
    node[p].sum = node[p << 1].sum + node[p << 1 | 1].sum;
}

// 把结点 p 的整段区间（长度是 len）都加上 v
void apply_add(int p, int len, ll v) {
    node[p].sum += v * len;
    node[p].tag += v;
}

// 下推：把结点 p 的标记加到两个儿子上，并清空自己的标记
void push_down(int p, int l, int r) {
    if (node[p].tag == 0) return;
    int mid = (l + r) >> 1;
    apply_add(p << 1, mid - l + 1, node[p].tag);
    apply_add(p << 1 | 1, r - mid, node[p].tag);
    node[p].tag = 0;
}

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

// 区间加：把 [ql, qr] 内每个数加上 v
void range_add(int p, int l, int r, int ql, int qr, ll v) {
    if (ql <= l && r <= qr) {
        apply_add(p, r - l + 1, v);
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) range_add(p << 1, l, mid, ql, qr, v);
    if (qr > mid) range_add(p << 1 | 1, mid + 1, r, ql, qr, v);
    push_up(p);
}

// 区间和：[ql, qr] 内所有数之和
ll range_sum(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return node[p].sum;
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    ll answer = 0;
    if (ql <= mid) answer += range_sum(p << 1, l, mid, ql, qr);
    if (qr > mid) answer += range_sum(p << 1 | 1, mid + 1, r, ql, qr);
    return answer;
}

// 单点赋值：把下标 pos 的数改成 v。先把沿路的标记推下去，叶子自己就是真实值
void point_assign(int p, int l, int r, int pos, ll v) {
    if (l == r) {
        node[p].sum = v;
        node[p].tag = 0;
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    if (pos <= mid) point_assign(p << 1, l, mid, pos, v);
    else point_assign(p << 1 | 1, mid + 1, r, pos, v);
    push_up(p);
}

// 线段树二分：在 [ql, qr] 里找第一个使 a[ql] + ... + a[i] >= d 的下标 i，找不到返回 0。
// need = d - (a[ql] + ... + a[l-1]) 表示"还差多少"，扫过一整段就把它从 need 里扣掉，
// 于是每层只会往一条路走，单次询问 O(log n)。
// 调用前保证 [ql, qr] 与结点区间相交。
int find_first(int p, int l, int r, int ql, int qr, ll &need) {
    if (ql <= l && r <= qr) {
        if (node[p].sum < need) {  // 整段加起来都不够，整段跳过
            need -= node[p].sum;
            return 0;
        }
        if (l == r) return l;  // 叶子：加上 a[l] 后前缀和终于达到 d
        push_down(p, l, r);    // 要往下走，儿子的值必须先变成真实值
        int mid = (l + r) >> 1;
        int res = find_first(p << 1, l, mid, ql, qr, need);
        if (res != 0) return res;
        return find_first(p << 1 | 1, mid + 1, r, ql, qr, need);
    }
    push_down(p, l, r);
    int mid = (l + r) >> 1;
    int res = 0;
    if (ql <= mid) res = find_first(p << 1, l, mid, ql, qr, need);
    if (res == 0 && qr > mid) res = find_first(p << 1 | 1, mid + 1, r, ql, qr, need);
    return res;
}

int main() {
    n = (int)read_int();
    m = (int)read_int();
    for (int i = 1; i <= n; i++) a[i] = read_int();

    build(1, 1, n);

    for (int step = 1; step <= m; step++) {
        int op = (int)read_int();
        if (op == 1) {
            int x = (int)read_int();
            int y = (int)read_int();
            ll v = read_int();
            range_add(1, 1, n, x, y, v);
        } else if (op == 2) {
            int x = (int)read_int();
            int y = (int)read_int();
            printf("%lld\n", range_sum(1, 1, n, x, y));
        } else if (op == 3) {
            int x = (int)read_int();
            int y = (int)read_int();
            ll d = read_int();
            ll need = d;  // 还没累加过任何元素
            int answer = find_first(1, 1, n, x, y, need);
            if (answer == 0) answer = y + 1;  // [x, y] 里都到不了 d
            printf("%d\n", answer);
        } else {
            int x = (int)read_int();
            ll d = read_int();
            point_assign(1, 1, n, x, d);
        }
    }
    return 0;
}

代码里有两处和上面的说明有关, 单独提一下:

读入用 fread 手写快读. 本题最多 $5 \times 10^6$ 个整数, 1s 时限下 cin 会明显拖慢.
结点用 struct Node { ll sum; ll tag; } 聚合成一个数组, 让 sum 和 tag 落在同一条缓存行里, 比开两个平行数组快.

复杂度

时间: 每次操作 $O(\log n)$ , 建树 $O(n)$ , 总 $O((n+m) \log n)$ .
空间: 线段树 $4n$ 个结点, 每个 16 字节, $n = 10^6$ 时约 64 MiB.
常数: 用上面这份代码对 $n = 10^6$ 的随机询问统计 find_first 的结点访问次数, 1e6 次询问里单次最多访问 57 个结点, 约为 $3\log_2 n$ , 和上面的 $O(\log n)$ 分析对得上. 四种操作里区间加最重(每次要走两条边界路径再上推), 卡时限时优先压它的常数.

总结

本题是两件事叠在一起:

区间加、区间和、单点赋值交给懒标记线段树, 这是线段树模板题的原样动作.
区间查找交给"线段树上的二分": 把"前缀和满不满足"换成"还差多少", 一整段能整段跳过就整段跳过, 于是查找从扫区间变成走一条 $O(\log n)$ 的路径.

整段跳过的依据是段内前缀和不减, 也就是元素非负, 这刚好和题面"在前缀和上做 lower_bound"的描述一致. 数据里一旦允许负数, 这条推理失效, 需要换成一棵维护区间最大前缀和的树, 而那种信息没法承受区间加的懒标记.

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

为什么要求元素非负

样例上的执行过程

代码

复杂度

总结