Hexo
0%

线段树

Posted on In ,
Symbols count in article: 6.7k Reading time ≈ 6 mins.

线段树

模板1

将某区间每个数加上k

求出某区间每一个数的和

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
128
129
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
ll n, m, a[maxn], t[maxn << 2], tag[maxn << 2]; // t为节点数组，tag为懒标记数组

ll ls(ll x)
{
    return x << 1;
}
ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p) // 更新当前节点
{
    t[p] = t[ls(p)] + t[rs(p)];
    return;
}

void f(ll p, ll l, ll r, ll k) // 修改
{
    tag[p] = tag[p] + k;
    t[p] = t[p] + k * (r - l + 1);
}

void push_down(ll p, ll l, ll r) // 向下一层更新
{
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, tag[p]);
    f(rs(p), mid + 1, r, tag[p]);
    tag[p] = 0; // 懒标记清零
}

void build_tree(ll l, ll r, ll p) // 建树
{
    tag[p] = 0;
    if (l == r)
    {
        t[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1; // 中间分割点
    build_tree(l, mid, p << 1);
    build_tree(mid + 1, r, (p << 1) | 1);
    push_up(p);
}

/*
nl,nr为要修改的区间
l,r为固定的区间
p为节点编号
k为修改的值
*/
void update(ll nl, ll nr, ll l, ll r, ll p, ll k)
{
    if (nl <= l && r <= nr)
    {
        t[p] += k * (r - l + 1);
        tag[p] += k;
        return;
    }
    push_down(p, l, r);
    ll mid = (l + r) >> 1;
    if (nl <= mid)
        update(nl, nr, l, mid, ls(p), k);
    if (nr > mid)
        update(nl, nr, mid + 1, r, rs(p), k);
    push_up(p);
}

/*
ql,qr为询问区间
l,r为固定区间
p为节点编号
*/
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    ll res = 0;
    if (ql <= l && r <= qr)
        return t[p];
    ll mid = (l + r) >> 1;
    push_down(p, l, r); // 更新下面一层的节点
    if (ql <= mid)
        res += query(ql, qr, l, mid, ls(p));
    if (qr > mid)
        res += query(ql, qr, mid + 1, r, rs(p));
    return res;
}

void solve()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while (m--)
    {
        ll ope;
        cin >> ope;
        if (ope == 1) // 修改[l,r]的每个值加上k
        {
            ll l, r, k;
            cin >> l >> r >> k;
            update(l, r, 1, n, 1, k);
        }
        else
        {
            ll l, r;
            cin >> l >> r;
            cout << query(l, r, 1, n, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

模板2

将某区间每一个数乘上x

将某区间每一个数加上x

求某区间每一个数的和

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
const int mod = 1e9;
ll n, q, m, a[maxn];
struct nopde
{
    ll v, mul, add; // mul,add都是标记
} t[maxn << 2];

ll ls(ll x)
{
    return x << 1;
}

ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p)
{
    t[p].v = (t[ls(p)].v + t[rs(p)].v) % mod;
    return;
}

void build_tree(ll l, ll r, ll p)
{
    t[p].mul = 1;
    t[p].add = 0;
    if (l == r)
    {
        t[p].v = a[l] % mod;
        return;
    }
    ll mid = (l + r) >> 1;
    build_tree(l, mid, ls(p));
    build_tree(mid + 1, r, rs(p));
    push_up(p);
    return;
}
/*
维护lazytag
*/
void push_down(ll l, ll r, ll p)
{
    ll mid = (l + r) >> 1;
    // 儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
    t[ls(p)].v = (t[ls(p)].v * t[p].mul + t[p].add * (mid - l + 1)) % mod;
    t[rs(p)].v = (t[rs(p)].v * t[p].mul + t[p].add * (r - mid)) % mod;
    // 维护lazytag
    t[ls(p)].mul = (t[ls(p)].mul * t[p].mul) % mod;
    t[rs(p)].mul = (t[rs(p)].mul * t[p].mul) % mod;
    t[ls(p)].add = (t[ls(p)].add * t[p].mul + t[p].add) % mod;
    t[rs(p)].add = (t[rs(p)].add * t[p].mul + t[p].add) % mod;
    // 初始化父节点
    t[p].mul = 1;
    t[p].add = 0;
    return;
}

//乘上k
void mul(ll ml, ll mr, ll l, ll r, ll p, ll k)
{
    if (mr < l || r < ml)
        return;
    if (ml <= l && r <= mr)
    {
        t[p].v = (t[p].v * k) % mod;
        t[p].mul = (t[p].mul * k) % mod;
        t[p].add = (t[p].add * k) % mod;
        return;
    }
    // 先传递lazytag
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    mul(ml, mr, l, mid, ls(p), k);
    mul(ml, mr, mid + 1, r, rs(p), k);
    push_up(p);
    return;
}

//加上k
void add(ll al, ll ar, ll l, ll r, ll p, ll k)
{
    if (ar < l || r < al)
        return;
    if (al <= l && r <= ar)
    {
        t[p].v = (t[p].v + k * (r - l + 1)) % mod;
        t[p].add = (t[p].add + k) % mod;
        return;
    }
    // 先传递lazytag
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    add(al, ar, l, mid, ls(p), k);
    add(al, ar, mid + 1, r, rs(p), k);
    push_up(p);
    return;
}

ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (qr < l || r < ql)
        return 0;
    if (ql <= l && r <= qr)
        return t[p].v;
    push_down(l, r, p);
    ll mid = (l + r) >> 1;
    return (query(ql, qr, l, mid, ls(p)) + query(ql, qr, mid + 1, r, rs(p))) % mod;
}
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while (q--)
    {
        int ope;
        cin >> ope;
        if (ope == 1) // 在[l,r]区间每个数都乘k
        {
            int l, r, k;
            cin >> l >> r >> k;
            mul(l, r, 1, n, 1, k);
        }
        else if (ope == 2) // 在[l,r]区间每个数都加k
        {
            int l, r, k;
            cin >> l >> r >> k;
            add(l, r, 1, n, 1, k);
        }
        else // 询问区间和
        {
            int l, r;
            cin >> l >> r;
            cout << query(l, r, 1, n, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}

模板3

将区间的所有值修改为x

求出区间和

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
ll n, m, a[maxn], t[maxn << 2], tag[maxn << 2];

ll ls(ll x)
{
    return x << 1;
}
ll rs(ll x)
{
    return x << 1 | 1;
}

void push_up(ll p)
{
    t[p] = t[ls(p)] + t[rs(p)];
}

void push_down(int l, int r, int p)
{
    if (tag[p])
    {
        int mid = (l + r) >> 1;
        t[ls(p)] = tag[p] * (mid - l + 1);
        t[rs(p)] = tag[p] * (r - mid);
        tag[ls(p)] = tag[p];
        tag[(rs(p))] = tag[p];
        tag[p] = 0;
    }
}

void build_tree(int l, int r, int p)
{
    if (l == r)
    {
        t[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build_tree(l, mid, ls(p));
    build_tree(mid + 1, r, rs(p));
    push_up(p);
}

void update(int l, int r, int ul, int ur, int p, int k)
{
    if (ul <= l && r <= ur)
    {
        t[p] = k * (r - l + 1);
        tag[p] = k;
        return;
    }
    if (tag[p])
        push_down(l, r, p);
    ll mid = (l + r) >> 1;
    if (ul <= mid)
        update(l, mid, ul, ur, ls(p), k);
    if (ur > mid)
        update(mid + 1, r, ul, ur, rs(p), k);
    push_up(p);
}

ll query(int l, int r, int ql, int qr, int p)
{
    if (ql <= l && r <= qr)
        return t[p];
    if (tag[p])
        push_down(l, r, p);
    int mid = (l + r) >> 1;
    ll sum = 0;
    if (ql <= mid)
        sum += query(l, mid, ql, qr, ls(p));
    if (qr > mid)
        sum += query(mid + 1, r, ql, qr, rs(p));
    return sum;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    build_tree(1, n, 1);
    while(m--)
    {
        int ope;
        cin >> ope;
        if(ope==1)//将区间[l,r]的每个值修改为k
        {
            int l, r, k;
            cin >> l >> r >> k;
            update(1, n, l, r, 1, k);
        }
        else//询问[l,r]的区间和
        {
            int l, r;
            cin >> l >> r;
            cout << query(1, n, l, r, 1) << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}