线段树

sdjasj
  2023-02-01 16:38:19 2023-02-01 16:38 撰寫   2023-02-01 17:49:13 2023-02-01 17:49 更新    2.8k 字數  15 分鐘

单点修改区间查询

区间和

给定长度为$N$的数列$A$，以及$M$条指令，每条指令可能是以下两种之一：

  1. 1 x y，查询区间$[x,y]$ 中的最大连续子段和
  2. 2 x y，把$A[x]$改成 $y$。

对于每个查询指令，输出一个整数表示答案。

输入格式

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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 5e5 + 7;

typedef struct {
    int l, r;
    int lmax, rmax, sum, tmax;
} Node;

Node t[4 * N];
int a[N];

void pushup(int u) {
    Node& root = t[u], left = t[u * 2], right = t[u * 2 + 1];
    root.lmax = max(left.lmax, left.sum + right.lmax);
    root.rmax = max(right.rmax, right.sum + left.rmax);
    root.sum = left.sum + right.sum;
    root.tmax = max(left.tmax, max(right.tmax, left.rmax + right.lmax));
}

void pushup(Node& root, Node& left, Node& right) {
    root.lmax = max(left.lmax, left.sum + right.lmax);
    root.rmax = max(right.rmax, right.sum + left.rmax);
    root.sum = left.sum + right.sum;
    root.tmax = max(left.tmax, max(right.tmax, left.rmax + right.lmax));
}

void build(int u, int l, int r) {
    t[u] = {l, r};
    if (l == r) {
        t[u].sum = t[u].lmax = t[u].rmax = t[u].tmax = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    pushup(u);
}

Node query(int u, int l, int r) {
    if (t[u].l >= l && t[u].r <= r) {
        return t[u];
    }
    int mid = t[u].l + t[u].r >> 1;
    if (r <= mid) {
        return query(u * 2, l, r);
    }
    if (l > mid) {
        return query(u * 2 + 1, l, r);
    }
    Node res;
    Node left = query(u * 2, l , r);
    Node right = query(u * 2 + 1, l, r);
    pushup(res, left, right);
    return res;
}

void modify(int u, int y, int x) {
    if (t[u].l == y && t[u].r == y) {
        t[u].lmax = t[u].rmax = t[u].sum = t[u].tmax = x;
        return;
    }

    int mid = t[u].l + t[u].r >> 1;
    if (y <= mid) {
        modify(u * 2, y, x);
    } else {
        modify(u * 2 + 1, y, x);
    }
    pushup(u);
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    while (m--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            if (x > y) swap(x, y);
            cout << query(1, x, y).tmax << endl;
        } else {
            modify(1, x, y);
        }
    }
    return 0;
}

区间最大值

给定一个正整数数列$a_1,a_2,…,a_n$，每一个数都在 $0 \sim p-1$ 之间。

可以对这列数进行两种操作：

  1. 添加操作：向序列后添加一个数，序列长度变成 $n+1$；
  2. 询问操作：询问这个序列中最后$L$个数中最大的数是多少。

程序运行的最开始，整数序列为空。

一共要对整数序列进行$m$次操作。

写一个程序，读入操作的序列，并输出询问操作的答案

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200007;

struct {
	int l;
	int r;
	int v;
} t[N * 4];

int m, p, n, a;

void pushup(int u) {
	t[u].v = max(t[u << 1].v, t[u << 1 | 1].v);
}

void build(int u, int l, int r) {
    t[u] = {l, r};
    if (l == r) return;
	int mid = l + r  >> 1;
	build(u << 1, l ,mid);
	build(u << 1 | 1, mid + 1, r);
}

void update(int u, int x, int v) {
	if (t[u].l == x && t[u].r == x) t[u].v = v;
	else {
			
		int mid = t[u].l + t[u].r >> 1;
		if (mid >= x) update(u << 1, x, v);
		else update(u << 1 | 1, x, v);
		pushup(u);
	}
}

int query(int u, int l, int r) {
	if (l <= t[u].l && r >= t[u].r) return t[u].v;
	int ans = 0;
	int mid  = t[u].l + t[u].r >> 1;
	if (l <= mid) ans = query(u << 1, l ,r);
	if (r > mid) ans = max(ans, query(u << 1 | 1, l ,r));
	return ans; 
}

int main() {
	cin >> m >>p;
	build(1, 1, m);
	while (m--) {
		char op[2];
		int x;
		scanf("%s%d", op, &x);
		if (*op == 'Q') {
			a = query(1, n - x + 1, n);
			cout << a << endl;
		} else {
			update(1, ++n, ((LL)x + a) % p);
		}
	}
	return 0;	
}

区间gcd

给定一个长度为 N的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把$ A[l],A[l+1],…,A[r] $都加上 。
  2. Q l r，表示询问$ A[l],A[l+1],…,A[r] $的最大公约数(GCD)。

对于每个询问，输出一个整数表示答案。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node
{
    int l, r;
    LL sum, d;
}tr[N * 4];

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        LL b = w[r] - w[r - 1];
        tr[u] = {l, r, b, b};
    }
    else
    {
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

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

    int l, r;
    LL d;
    char op[2];
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            auto left = query(1, 1, l);
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);
            printf("%lld\n", abs(gcd(left.sum, right.d)));
        }
        else
        {
            scanf("%lld", &d);
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);
        }
    }

    return 0;
}

区间修改区间查询（懒标记）

区间和（区间加）

给定一个长度为 N的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

  1. C l r d，表示把 $A[l],A[l+1],…,A[r] $都加上 d。
  2. Q l r，表示询问数列中第 $l\sim r$个数的和。

对于每个询问，输出一个整数表示答案。

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
#include <vector>
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
struct Node {
    int l, r;
    LL sum, add;
} tr[4 * N];
int a[N];

void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
    Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add;
        left.sum += (LL)(left.r - left.l + 1) * root.add;
        right.add += root.add;
        right.sum += (LL) (right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, a[l], 0};
    } else {
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
        tr[u].add = 0;
    }
}

void modify(int u, int l, int r, int x) {
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].sum += (LL) x * (tr[u].r - tr[u].l + 1);
        tr[u].add += x;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if (l <= mid) {
        modify(u << 1, l, r, x);
    }
    if (r > mid) {
        modify(u << 1 | 1, l, r, x);
    }
    pushup(u);
}

LL query(int u, int l, int r) {
    if (l <= tr[u].l && r >= tr[u].r) {
        return tr[u].sum;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    LL ans = 0;
    pushdown(u);
    if (l <= mid) ans += query(u << 1, l, r);
    if (r > mid) ans += query(u << 1 | 1, l, r);
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    while (m--) {
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l , &r);
        if (op[0] == 'Q') {
            cout << query(1, l, r) << endl;
        } else {
            scanf("%d", &d);
            modify(1, l, r, d);
        }
    }
    return 0;
}

区间和（区间乘和加）

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。

有长为 N 的数列，不妨设为 $a_1,a_2,…,a_N$。

有如下三种操作形式：

  1. 把数列中的一段数全部乘一个值；
  2. 把数列中的一段数全部加一个值；
  3. 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P的值。
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
#include <vector>
#include <iostream>
#include <cstdio>
#include <unordered_map>
#include <map>
#include <unordered_set>
using namespace std;
typedef long long LL;
const int N = 1e5 + 7;
int p;
struct Node {
    int l, r;
    LL sum, add, mul;
} tr[4 * N];
int a[N];

void cal(int u, LL add, LL mul) {
    tr[u].sum = ((LL) tr[u].sum * mul + (LL) (tr[u].r - tr[u].l + 1) * add) % p;
    tr[u].mul = (LL) (tr[u].mul * mul) % p;
    tr[u].add = ((LL) (tr[u].add * mul) % p + add) % p;
}

void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown(int u) {
    cal(u << 1, tr[u].add, tr[u].mul);
    cal(u << 1 | 1, tr[u].add, tr[u].mul);
    tr[u].add = 0, tr[u].mul = 1;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = {l, r, a[l], 0, 1};
    } else {
        tr[u] = {l, r, 0, 0, 1};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int add, int mul) {
    if (l <= tr[u].l && r >= tr[u].r) {
        cal(u, add, mul);
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(u);
    if (l <= mid) {
        modify(u << 1, l, r, add, mul);
    }
    if (r > mid) {
        modify(u << 1 | 1, l, r, add, mul);
    }
    pushup(u);
}

LL query(int u, int l, int r) {
    if (l <= tr[u].l && r >= tr[u].r) {
        return tr[u].sum;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    LL ans = 0;
    pushdown(u);
    if (l <= mid) ans = query(u << 1, l, r) % p;
    if (r > mid) ans = (ans + query(u << 1 | 1, l, r)) % p;
    return ans;
}

int main() {
    int n, m;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    cin >> m;
    build(1, 1, n);
    while (m--) {
        int op;
        int l, r, d;
        scanf("%d%d%d", &op, &l , &r);
        if (op == 1) {
            scanf("%d", &d);
            modify(1, l, r, 0, d);
        } else if (op == 2) {
            scanf("%d", &d);
            modify(1, l, r, d, 1);
        } else {
            cout << query(1, l, r) << endl;
        }
    }
    return 0;
}

应用

1.区间和

左右子区间相加即可

2.区间最大数

左右区间最大数取max

3.区间最大子段和

左区间左端点开始的最大子段和 右区间右端点开始的最大子段和 左区间右端点开始的最大子段和+右区间左端点开始的最大子段和 三者取max

  • 標題: 线段树
  • 作者: sdjasj
  • 撰寫于: 2023-02-01 16:38:19
  • 更新于: 2023-02-01 17:49:13
  • 連結: https://redefine.ohevan.com/2023/02/01/线段树/
  • 版權宣告: 本作品采用 CC BY-NC-SA 4.0 进行许可。
 留言
此頁目錄
线段树
  1. 单点修改区间查询
  2. 区间修改区间查询（懒标记）
  • 应用