2025-02-12线段树（单点修改）

线段树(单点修改)

主要内容

b907982af472b92e58493a275858e38

  • 注意：若只涉及到单点修改，则不需要pushdown（懒加载）操作。

例题

最大数

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
// http://ybt.ssoier.cn:8088/problem_show.php?pid=1549

/**
 * 单点修改， (没涉及到区间修改，所以不需要懒标记pushdown操作)
 * 区间查询
*/

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

const int M=2e5+10;
struct Node{
    int l, r;
    int v;
}tr[4*M];

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

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

int query(int u, int l, int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;

    int v=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) v=query(u<<1, l, r);
    if(r>mid) v=max(v, query(u<<1|1, l, r));

    return v;
}

void modify(int u, int x, int v){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].v=v;
        return;
    } 

    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);
}

int m, p, a=0, n=0;

void work(){
    scanf("%d%d", &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);
            printf("%d\n", a);
        }else{
            n++;
            int v=(a+x)%p;
            modify(1, n, v);
        }
    }
}

int main(){
    work();
    return 0;
}

你能回答这些问题吗

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
// https://www.acwing.com/problem/content/246/

/**
 * 依旧是单点修改，
 * 区间查询
 * 
 * 但是涉及的到维护多个值
 * 针对一个区间u，左半区间l，右半区间r
 * 要求的连续最大连续子段和有三种情况
 * 其中两种是等于左半区间或右半区间的最大子段和
 * 剩下只可能横跨两个区间，
 * 此时最大连续子段和等于左半的最大靠右连续子段和加上右半最大靠左连续子段和
*/

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

int n, m;
const int N=5e5+10;
struct Node{
    int l, r;
    int v, sum, lv, rv;
}tr[4*N];
int a[N];

void pushup(Node& u, Node& l, Node& r){
    //更新单独封装出一个函数，可以复用
    u.sum=l.sum+r.sum;
    u.lv=max(l.lv, l.sum+r.lv);
    u.rv=max(r.rv, r.sum+l.rv);
    u.v=max(max(l.v, r.v), l.rv+r.lv);
}

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

void build(int u, int l, int r){
    tr[u].l=l, tr[u].r=r;

    if(l==r){
        tr[u].sum=tr[u].lv=tr[u].rv=tr[u].v=a[l];
        return;
    }

    int mid=l+r>>1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);
    pushup(u);
}

Node query(int u, int l, int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];

    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{
        Node res=Node(), lres=query(u<<1, l, r), rres=query(u<<1|1, l, r);
        pushup(res, lres, rres);
        return res;
    }
}

void modify(int u, int x, int v){
    if(tr[u].l==x&&tr[u].r==x) {
        tr[u].sum = tr[u].lv = tr[u].rv = tr[u].v = v;
        return;
    }

    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);
}

void work(){
    scanf("%d%d", &n, &m);

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

    build(1, 1, n);

    while(m--){
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);

        if(k==1){
            int tmp=max(x, y);
            x=min(x, y);
            y=tmp;
            Node res=query(1, x, y);
            printf("%d\n", res.v);
        }else{
            modify(1, x, y);
        }
    }
}

int main(){
    work();
    return 0;
}

区间最大公约数

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
// https://www.acwing.com/problem/content/description/247/

/**
 * 本题表面上是区间更新
 * 实际上如果直接维护a数组，区间每个元素都加上d，根本无法维护gcd
 * 
 * 这里要使用到gcd的性质：
 * res=gcd(a[l], a[l+1], a[l+2], ..., a[r]) = gcd(a[l], a[l+1]-a[l], a[l+2]-a[l+1], ..., a[r]-a[r-1])
 * (线性变换不改变gcd)
 * 
 * 进一步地， res=gcd(a[l], gcd(diff[l+1], diff[l+2], ..., diff[r]))
 * 所以用线段树维护差分数组，就可以把区间更新变成单点更新
 * 维护区间gcd, 还有区间和sum
*/

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

typedef long long ll;

ll gcd(ll a, ll b) {
	return __gcd(a, b);
}

const int N=5e5+10;
struct Node{
    int l, r;
    ll sum, gcd;
}tr[4*N];

ll a[N];

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

void build(int u, int l, int r){
    tr[u]={l, r};

    if(l==r){
        tr[u].sum=tr[u].gcd=a[l]-a[l-1];//a的差分
        return;
    }

    int mid=l+r>>1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);

    pushup(u);
}

ll query_sum(int u, int l, int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    int mid=tr[u].l+tr[u].r>>1;
    ll res=0;
    if(l<=mid) res+=query_sum(u<<1, l, r);
    if(r>mid) res+=query_sum(u<<1|1, l, r);

    return res;
}

ll query_gcd(int u, int l, int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].gcd;

    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query_gcd(u<<1, l, r);
    else if(l>mid) return query_gcd(u<<1|1, l, r);
    else return gcd(query_gcd(u<<1, l, r), query_gcd(u<<1|1, l, r));
}

void modify(int u, int x, ll add){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].sum+=add;
        tr[u].gcd+=add;
        return;
    }

    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid) modify(u<<1, x, add);
    else modify(u<<1|1, x, add);

    pushup(u);
}

int n, m;

void work(){
    scanf("%d%d", &n, &m);

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

    build(1, 1, n);

    while(m--){
        char op[2];
        scanf("%s", op);

        if(*op=='C'){
            int l, r;
            ll d;
            scanf("%d%d%lld", &l, &r, &d);

            modify(1, l, d);
            if(r+1<=n) modify(1, r+1, -d);//差分在n+1处减没有实际意义，而且会导致越界！！！
        }else{
            int l, r;
            scanf("%d%d", &l, &r);

            ll x=query_sum(1, 1, l);
            ll y;
            if(l+1<=r) y=query_gcd(1, l+1, r);//一定要保证区间是合法的！！！
            else y=x;//当区间只有一个元素时，根本就没有后面的差分

            ll res=gcd(x, y);

            printf("%lld\n", abs(res));//差分可能有负数
        }
    }
}

int main(){
    work();
    // printf("%lld", gcd(1, 2));
    return 0;
}
寒假练题计划 > 提高算法 > 数据结构 > 线段树
#cpp #algorithm #ACwing #binary search #segment tree #gcd
2025-02-12线段树（单点修改）
http://666xz666.github.io/2025/02/12/线段树（单点修改）/
作者
666xz666
发布于
2025年2月12日
许可协议