寂静的角落 星空在前,路在脚下
标记永久化线段树
发布于: 2021-04-07 更新于: 2021-04-07 分类于: 数据结构 阅读次数: 

$\color{Green}code - oi$

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
#include <algorithm>
using namespace std;
typedef long long ll;
inline int ls(int f) { return f << 1; }
inline int rs(int f) { return f << 1 | 1; }
inline int mid(int l, int r) { return (l + r) >> 1; }
const int maxn = 1e5 + 5;
ll a[maxn];
struct node {
ll v;
ll add;
node() : add(0) {}
} st[maxn << 2];
inline void push_up(int p) { st[p].v = st[ls(p)].v + st[rs(p)].v; }
void build(int p, int l, int r) {
if (l == r)
st[p].v = a[l];
else {
int m = mid(l, r);
build(ls(p), l, m);
build(rs(p), m + 1, r);
push_up(p);
}
}

void plus(int p, int nl, int nr, int cl, int cr, ll k) {
if (nr < cl || cr < nl) return;
if (cl <= nl && nr <= cr) {
st[p].v = st[p].v + k * (nr - nl + 1);
st[p].add = st[p].add + k;
return;
}
st[p].v += k * (min(nr, cr) - max(nl, cl) + 1);
int m = mid(nl, nr);
plus(ls(p), nl, m, cl, cr, k);
plus(rs(p), m + 1, nr, cl, cr, k);
}
ll query(int p, int nl, int nr, int ql, int qr, ll tag) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return st[p].v + tag * (nr - nl + 1);
int m = mid(nl, nr);
return query(ls(p), nl, m, ql, qr, tag + st[p].add) +
query(rs(p), m + 1, nr, ql, qr, tag + st[p].add);
}

$\color{Green}code - poject$

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
template <class T>
class segment_tree {
private:
inline int _ls(int f) { return f << 1; }
inline int _rs(int f) { return f << 1 | 1; }
inline int _mid(int l, int r) { return (l + r) >> 1; }
inline int _max(const int &a, const int &b) { return (a > b) ? a : b; }
inline int _min(const int &a, const int &b) { return (a < b) ? a : b; }
T *_a;
T _n;
struct node {
T v;
T add;
node() : add(0) {}
} * _st;
inline void push_up(int p) { _st[p].v = _st[_ls(p)].v + _st[_rs(p)].v; }
void build(int p, int l, int r) {
if (l == r)
_st[p].v = _a[l];
else {
int m = _mid(l, r);
build(_ls(p), l, m);
build(_rs(p), m + 1, r);
push_up(p);
}
}
void _plus(int p, int nl, int nr, int cl, int cr, T k) {
if (nr < cl || cr < nl) return;
if (cl <= nl && nr <= cr) {
_st[p].v += k * (nr - nl + 1);
_st[p].add += k;
return;
}
_st[p].v += k * (_min(nr, cr) - _max(nl, cl) + 1);
int m = _mid(nl, nr);
_plus(_ls(p), nl, m, cl, cr, k);
_plus(_rs(p), m + 1, nr, cl, cr, k);
}
T _query(int p, int nl, int nr, int ql, int qr, T tag) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return _st[p].v + tag * (nr - nl + 1);
int m = _mid(nl, nr);
return _query(_ls(p), nl, m, ql, qr, tag + _st[p].add) +
_query(_rs(p), m + 1, nr, ql, qr, tag + _st[p].add);
}

public:
segment_tree(T n, T *a) : _n(n), _a(a) {
_st = new node[n << 2];
build(1, 1, _n);
}
~segment_tree() { delete[] _st; }
inline void plus(int l, int r, T k) { _plus(1, 1, _n, l, r, k); }
inline T query(int l, int r) { return _query(1, 1, _n, l, r, 0); }
};
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证