线段树

线段树

能实现快速的区间查询、区间修改的数据结构。

实现区间修改、区间查询等操作的时间复杂度为 $O(\log N)$。

可以用来维护区间最大值、区间和、区间异或和等等。实际上，线段树的原理决定了其可以维护一切符合结合律的信息。（不符合结合律的运算？比方说，浮点数加法）

很长、不是很好写，如果没有区间修改需要可以写树状数组。

例题

CF213769A

建树

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

const int N = 5e5;
#define ls(X) ((X) << 1)
#define rs(X) ((X) << 1 | 1)
// <------------------------------>
int a[N]; // 原始数据
struct
{
    int l, r, v;
} f[N << 2]; // 节点数需要乘4

void push_up(int pos)
{
    // 将指定操作向上（向根）传递
    f[pos].v = f[ls(pos)].v + f[rs(pos)].v;
}

void build(int pos, int l, int r)
{
    f[pos].l = l, f[pos].r = r;
    if (l == r)
    {
        // 这里是树的叶子节点，对他直接赋值
        f[pos].v = a[l];
        return;
    }
    // 对子树递归建树
    int mid = (l + r) / 2;
    build(ls(pos), l, mid);
    build(rs(pos), mid + 1, r);
    push_down(pos);
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
int query(int pos, int l, int r)
{
    if (f[pos].l >= l && f[pos].r <= r)
        return f[pos].v;
    // 二分查找
    int mid = (f[pos].l + f[pos].r) / 2;
    if (l > mid)
        return query(rs(pos), l, r);
    else if (r <= mid)
        return query(ls(pos), l, r);
    else
        return query(ls(pos), l, r) + query(rs(pos), l, r);
}

普通的修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void update(int pos, int l, int r, int k)
{
    if (f[pos].l >= l && f[pos].r <= r)
    {
        f[pos].t += k;
        f[pos].v += k * (r - l + 1);
        return;
    }
    int mid = (f[pos].l + f[pos].r) / 2;
    if (l > mid)
        update(rs(pos), l, r, k);
    else if (r <= mid)
        update(ls(pos), l, r, k);
    else
        update(ls(pos), l, mid, k), update(rs(pos), mid + 1, r, k);
    push_up(pos);
}

懒标记

当更新某一区间时，给维护该区间的节点打懒标记，不再把每个点都更新，以此实现优化。

1
2
3
4
5
struct node
{
    ll l, r, v, t; // t 用于存储懒标记
} f[N << 2];

push_down()维护懒标记。

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

inline void push_down(ll pos)
{
    if (!f[pos].t)
        return;
    // 向下传递懒标记
    f[ls(pos)].t += f[pos].t;
    f[rs(pos)].t += f[pos].t;
    int mid = (f[pos].l + f[pos].r) / 2;
    // 处理懒标记
    // 值 += 懒标记值 * 节点数
    f[ls(pos)].v += f[pos].t * (mid - f[ls(pos)].l + 1); 
    f[rs(pos)].v += f[pos].t * (f[rs(pos)].r - mid);
    // 去掉懒标记 因为已经传下去了
    f[pos].t = 0;
}

void update(int pos, int l, int r, ll k)
{
    if (f[pos].l >= l && f[pos].r <= r)
    {
        // 更新只与现在的节点有关
        f[pos].t += k; // 更新懒标记
        f[pos].v += k * (r - l + 1);
        return;
    }
    push_down(pos); // 注意
    int mid = (f[pos].l + f[pos].r) / 2;
    if (l > mid)
        update(rs(pos), l, r, k);
    else if (r <= mid)
        update(ls(pos), l, r, k);
    else
        update(ls(pos), l, mid, k), update(rs(pos), mid + 1, r, k);
    push_up(pos);
}

ll query(int pos, int l, int r)
{
    push_down(pos); // 注意
    if (f[pos].l >= l && f[pos].r <= r)
        return f[pos].v;
    int mid = (f[pos].l + f[pos].r) / 2;
    if (l > mid)
        return query(rs(pos), l, r);
    else if (r <= mid)
        return query(ls(pos), l, r);
    else
        return query(ls(pos), l, mid) + query(rs(pos), mid + 1, r);
}

板子

默认维护的是区间和。构造函数接受两个参数，原始数组大小和原始数组（long long）。

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
class SegTree
{
  private:
    void push_up(int pos)
    {
        // modify here
        f[pos].v = f[ls(pos)].v + f[rs(pos)].v;
    }
    inline void push_down(long long pos)
    {
        if (!f[pos].t)
            return;
        f[ls(pos)].t += f[pos].t;
        f[rs(pos)].t += f[pos].t;
        int mid = (f[pos].l + f[pos].r) / 2;
        f[ls(pos)].v += f[pos].t * (mid - f[ls(pos)].l + 1); // modify here
        f[rs(pos)].v += f[pos].t * (f[rs(pos)].r - mid);     // modify here
        f[pos].t = 0;
    }

  public:
    long long query(int pos, int l, int r)
    {
        push_down(pos);
        if (f[pos].l >= l && f[pos].r <= r)
            return f[pos].v;
        int mid = (f[pos].l + f[pos].r) / 2;
        if (l > mid)
            return query(rs(pos), l, r);
        else if (r <= mid)
            return query(ls(pos), l, r);
        else
            // modify here
            return query(ls(pos), l, mid) + query(rs(pos), mid + 1, r);
    }
    void update(int pos, int l, int r, long long k)
    {
        if (f[pos].l >= l && f[pos].r <= r)
        {
            f[pos].t += k;
            f[pos].v += k * (r - l + 1);
            return;
        }
        push_down(pos);
        int mid = (f[pos].l + f[pos].r) / 2;
        if (l > mid)
            update(rs(pos), l, r, k);
        else if (r <= mid)
            update(ls(pos), l, r, k);
        else
            update(ls(pos), l, mid, k), update(rs(pos), mid + 1, r, k);
        push_up(pos);
    }

    struct node
    {
        long long l, r, v, t;
    };
    long long *a;

    SegTree(long long s, long long *ori)
    {
        this->size = s;
        a = ori;
        f = (node *)malloc((s * 4 + 10) * sizeof(node));
        build(1, 1, s);
    }

  private:
    int size = 1e6 + 5;
    node *f;
    inline int ls(int p)
    {
        return p << 1;
    }
    inline int rs(int p)
    {
        return p << 1 | 1;
    }

    void build(int pos, int l, int r)
    {
        f[pos] = {l, r, 0, 0};
        if (l == r)
        {
            f[pos].v = a[l];
            return;
        }
        int mid = ((l + r) >> 1);
        build(ls(pos), l, mid);
        build(rs(pos), mid + 1, r);
        push_up(pos);
    }
};
Competitive Programming
#DS
线段树
https://a48zhang.github.io/2023/05/02/线段树/
作者
a48zhang
发布于
2023年5月2日
许可协议