我的算法书 - 值域线段树：查找第一个小于阈值的位置

一句话算法

把每个数值当成桶，桶里放这个数第一次出现的位置；要找第一个小于 $x$ 的位置，就查询值域 $(-\infty,x)$ 这些桶里的最小位置。

问题模型

给定一个长度为 $n$ 的数组 $a$ ，多次询问：

第一个满足 a[i] < x 的位置 i 是多少？

如果不存在这样的位置，输出 $n+1$ 。

例如数组为：

下标: 1  2  3  4  5  6  7
数值:10  5  8  4  5  9  3

询问 x = 5 时，小于 5 的位置有 4,7，第一个位置是 4。

单次询问直接从左到右扫描是 $O(n)$ 。如果询问很多，可以预处理每个值第一次出现的位置，再用线段树在值域上做最小值查询。

核心直觉

普通线段树通常维护“下标区间”。这道题换一个角度：维护“值域区间”。

对每个数值 $v$ ，定义：

first[v] = \min\{i \mid a_i = v\}

若 $v$ 没出现过，就令 $first[v]=+\infty$ 。

那么：

\text{第一个 } a_i < x \text{ 的位置} = \min_{v < x} first[v]

也就是说，原问题从“在数组里找位置”变成了“在值域里查询一段桶的最小值”。

为什么需要离散化

如果数组值很大，例如 $10^9$ ，不能直接开一个长度为 $10^9$ 的桶数组。

我们只关心数组中真正出现过的值，所以先把所有值排序去重：

原值:      3 4 5 8 9 10
压缩编号: 1 2 3 4 5 6

询问小于 $x$ 的值时，用 lower_bound 找到最后一个 < x 的压缩编号，然后在线段树上查询 [1,last_less] 的最小位置。

算法步骤

读入数组，把所有数放进 values。
对 values 排序去重，得到离散化后的值域。
建一棵维护最小值的线段树，初始值为 INF。
从左到右扫描数组：
- 找到 a[i] 的压缩编号 rank；
- 用 i 更新这个桶的最小值。
回答询问 x：
- last_less = lower_bound(values, x) - values.begin()；
- 查询压缩值域 [1,last_less] 的最小下标；
- 如果结果为 INF，输出 n+1。

算法证明

关键不变量：线段树的每个叶子维护某个数值第一次出现的位置，内部节点维护它所代表值域中所有叶子的最小位置。

预处理时，数组从左到右扫描。对值 $v$ 对应的叶子执行 min(当前值, i)，所以扫描结束后叶子正好等于 $first[v]$ 。内部节点每次由两个孩子取最小值，因此不变量成立。

对询问 $x$ ，所有满足 $a_i < x$ 的元素，其值一定落在值域区间 $(-\infty,x)$ 内；反过来，值域区间 $(-\infty,x)$ 中任意出现过的值，对应的位置也满足 $a_i < x$ 。

所以：

\begin{aligned} \text{答案} &= \min\{i \mid a_i < x\} \\ &= \min_{v < x} first[v] \end{aligned}

线段树查询的正是这个值域区间内的最小 first，因此答案正确。

复杂度分析

设数组长度为 $n$ ，询问数为 $q$ ，不同数值个数为 $V$ 。

离散化： $O(n\log n)$ 。
建立值域线段树： $O(n\log V)$ 。
每次询问： $O(\log V)$ 。
空间复杂度： $O(V)$ 。

如果只有一次询问，线性扫描 $O(n)$ 更简单；这个做法适合多次询问，或作为更复杂值域维护问题的子结构。

代码实现

模板输入格式：

n q
a1 a2 ... an
x1
x2
...
xq

每个询问输出第一个满足 a[i] < x 的位置；不存在时输出 n+1。

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

        #include <bits/stdc++.h>
using namespace std;

struct MinSegmentTree {
    static const int INF = 1e9;

    int n = 0;
    vector<int> tree;

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

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, INF);
    }

    void pull(int p) {
        tree[p] = min(tree[p << 1], tree[p << 1 | 1]);
    }

    void update_min(int pos, int value, int l, int r, int p = 1) {
        if (l == r) {
            tree[p] = min(tree[p], value);
            return;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) update_min(pos, value, l, mid, p << 1);
        else update_min(pos, value, mid + 1, r, p << 1 | 1);
        pull(p);
    }

    int query_min(int ql, int qr, int l, int r, int p = 1) const {
        if (ql > qr) return INF;
        if (ql <= l && r <= qr) return tree[p];

        int mid = (l + r) >> 1;
        int answer = INF;
        if (ql <= mid) answer = min(answer, query_min(ql, qr, l, mid, p << 1));
        if (qr > mid) answer = min(answer, query_min(ql, qr, mid + 1, r, p << 1 | 1));
        return answer;
    }
};

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

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    vector<int> values;
    values.reserve(n);

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

    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    MinSegmentTree seg((int)values.size());

    for (int i = 1; i <= n; i++) {
        int rank = lower_bound(values.begin(), values.end(), a[i]) - values.begin() + 1;
        seg.update_min(rank, i, 1, seg.n);
    }

    while (q--) {
        int x;
        cin >> x;

        // 所有小于 x 的值，正好落在压缩值域的 [1, last_less]。
        int last_less = lower_bound(values.begin(), values.end(), x) - values.begin();
        int pos = seg.query_min(1, last_less, 1, seg.n);

        if (pos == MinSegmentTree::INF) cout << n + 1 << '\n';
        else cout << pos << '\n';
    }

    return 0;
}

测试用例

输入：

7 4
10 5 8 4 5 9 3
5
4
11
1

输出：

解释：

< 5 的第一个位置是 4，值为 4。
< 4 的第一个位置是 7，值为 3。
< 11 的第一个位置是 1。
< 1 不存在，输出 n+1 = 8。

应用分类详解

这个技巧的本质是“在值域上维护位置最值”。看到题目既关心数值大小，又关心下标先后时，可以考虑把信息放到值域线段树里。

一、按值域筛选，返回最早位置

典型模式： 查询第一个小于、大于、不超过、不低于某个阈值的位置。

识别信号： 题目问“最早出现的位置”，但条件写在数值大小上。

核心建模： 每个值维护它第一次出现的位置，值域区间查询最小位置。

应用场景	经典题目	核心思路
第一个小于阈值的位置	本页模型	查询值域 `(-inf,x)` 的最小下标
第一个大于阈值的位置	本页变体	查询值域 `(x,+inf)` 的最小下标
第一个落在值域区间的位置	本页变体	查询值域 `[L,R]` 的最小下标

二、离线处理静态数组的多次阈值询问

典型模式： 数组不变，询问很多，每次阈值不同。

识别信号： 没有修改操作，查询次数 $q$ 较大。

核心建模： 先预处理所有值第一次出现的位置，之后每个询问只做一次值域区间最小值。

三、值域线段树的入门变形

典型模式： 不维护出现次数，而维护某个值对应的附加信息。

识别信号： 值域是主要维度，叶子不是 count，而是“最早位置、最晚位置、最优代价”等。

核心建模： 只要值域区间的信息可以由左右孩子合并，就可以套线段树。

经典例题

1. 第一个小于阈值的位置

给定静态数组，多次询问第一个小于 $x$ 的位置。直接使用本页模板。

2. 第一个大于阈值的位置

把查询区间从 [1,last_less] 改成 [first_greater,V]，其中 first_greater = upper_bound(values, x) + 1。

3. 值域区间内最早出现的位置

每次询问给出 [L,R]，要求第一个满足 $L \le a_i \le R$ 的位置。离散化后查询对应值域区间的最小下标。