NOTE
notebook/ 路径下的文件均为自己整理的内容，按照知识点类别归纳整理。

二叉树#

二叉树的遍历#

数组存树#

[Luogu - B3642 二叉树的遍历](B3642 二叉树的遍历 - 洛谷)

二叉树的三种主要遍历方式都依赖于深度优先搜索（DFS），唯一的区别在于访问当前结点的时机：

前序遍历 (Preorder)：先访问根结点，再遍历左子树，最后遍历右子树。（根-左-右）
中序遍历 (Inorder)：先遍历左子树，再访问根结点，最后遍历右子树。（左-根-右）
后序遍历 (Postorder)：先遍历左子树，再遍历右子树，最后访问根结点。（左-右-根）

在这道题里我们使用两个数组存储每个节点的左右孩子节点编号即可，由于时限宽松，使用标准递归即可通过。

Code#

1
// Problem: Luogu B3642
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/B3642
4
// Time: 2026-05-05 09:59:29
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
typedef long long ll;
15
typedef unsigned long long ull;
16
typedef pair<int, int> pii;
17
typedef pair<double, double> pdd;
18
typedef pair<long long, long long> pll;
19

20
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
21
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
22
const int inf = 0x3f3f3f3f;
23
const int N = 1e6 + 10;
24

25
int l[N], r[N];
26

27
void preorder(int u)
28
{
29
    if (u == 0) // 0表示空节点
30
        return;
31

32
    cout << u << " ";
33
    preorder(l[u]);
34
    preorder(r[u]);
35
}
36

37
void inorder(int u)
38
{
39
    if (u == 0)
40
        return;
41

42
    inorder(l[u]);
43
    cout << u << " ";
44
    inorder(r[u]);
45
}
46

47
void postorder(int u)
48
{
49
    if (u == 0)
50
        return;
51

52
    postorder(l[u]);
53
    postorder(r[u]);
54
    cout << u << " ";
55
}
56

57
void solve()
58
{
59
    int n;
60
    cin >> n;
61

62
    for (int i = 1; i <= n; i++)
63
        cin >> l[i] >> r[i];
64

65
    preorder(1);
66
    cout << endl;
67

68
    inorder(1);
69
    cout << endl;
70

71
    postorder(1);
72
    cout << endl;
73
}
74

75
int main()
76
{
77
    fastio();
78

79
    int T = 1;
80
    // cin >> T;
81

82
    while (T--)
83
        solve();
84

85
    return 0;
86
}

离线二维数点#

NOTE
前置知识：树状数组，离线与在线

模板链接：Luogu - P10814 【模板】离线二维数点

思路#

我们可以把原数组 $a$ 中的每一个元素 $a[i] = v$ ，看作是二维平面上的一个点 $(X, Y) = (i, v)$ ，即横坐标是数组下标，纵坐标是元素大小。

那么，对于查询 l, r, x，它实际上是在问：

“在二维平面中，横坐标满足 $l \le X \le r$ ，且纵坐标满足 $Y \le x$ 的点，一共有多少个？”

这就是一个二维数点问题，也叫二维正交范围查询问题。

对于可以离线的二维数点问题，我们可以通过排序消掉一个维度。

我们考虑按照限制元素 $x$ 的大小从小到大排序，同时将数组中的所有元素按照数值大小从小到大排序。

既然现在查询的 $x$ 是递增的，我们把所有值 $\le x$ 的数组元素对应的下标 $i$ ，“激活”并加入到一个数据结构中。这个数据结构只需要维护一个信息：在 $[l, r]$ 这个区间里，当前一共激活了多少个下标。

对应的操作为单点增加（激活下标）和区间求和（统计个数），使用树状数组维护。

add(a[idx].id, 1); 的含义是将 id 号的元素标记为 $1$ ，表示满足条件，树状数组维护的是某个区间有多少个 $1$ 。

Code#

1
// Problem: Luogu P10814
2
// Contest: Luogu
3
// URL: https://www.luogu.com.cn/problem/P10814
4
// Time: 2026-05-13 18:40:11
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 2e6 + 5;
25

26
struct Element
27
{
28
    int id, val;
29
    bool operator<(const Element &other) const
30
    {
31
        return val < other.val;
32
    }
33
} a[N];
34

35
struct Query
36
{
37
    int id, l, r, x;
38
    bool operator<(const Query &other) const
39
    {
40
        return x < other.x;
41
    }
42
} q[N];
43

44
int tr[N], res[N], n, m;
45

46
int lowbit(int x)
47
{
48
    return x & -x;
49
}
50

51
void add(int i, int k)
52
{
53
    for (; i <= n; i += lowbit(i))
54
        tr[i] += k;
55
}
56

57
int query(int i)
58
{
59
    int res = 0;
60
    for (; i > 0; i -= lowbit(i))
61
        res += tr[i];
62
    return res;
63
}
64

65
void solve()
66
{
67
    cin >> n >> m;
68
    for (int i = 1; i <= n; i++)
69
    {
70
        int x;
71
        cin >> x;
72
        a[i] = {i, x};
73
    }
74

75
    for (int i = 1; i <= m; i++)
76
    {
77
        int l, r, x;
78
        cin >> l >> r >> x;
79
        q[i] = {i, l, r, x};
80
    }
81

82
    sort(a + 1, a + n + 1), sort(q + 1, q + m + 1);
83

84
    int idx = 1; // 未加入树状数组的最小元素
85
    for (int i = 1; i <= m; i++)
86
    {
87
        while (idx <= n && a[idx].val <= q[i].x) // 将所有<=当前查询x的元素加入树状数组
88
        {
89
            add(a[idx].id, 1);
90
            idx++;
91
        }
92

93
        // 此时树状数组所有的点都满足 val <= q[i].x
94
        // 直接查即可
95
        res[q[i].id] = query(q[i].r) - query(q[i].l - 1);
96
    }
97

98
    for (int i = 1; i <= m; i++)
99
        cout << res[i] << '\n';
100
}
101

102
int main()
103
{
104
    fastio();
105

106
    int T = 1;
107
    // cin >> T;
108

109
    while (T--)
110
        solve();
111

112
    return 0;
113
}