寂静的角落 星空在前,路在脚下
线段树 Segment Tree
发布于: 2021-04-06 更新于: 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
45
46
47
48
49
50
51
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);
}
}
inline void push_down(int p, int l, int r) {
int m = mid(l ,r);
st[ls(p)].v += st[p].add * (m - l + 1);
st[rs(p)].v += st[p].add * (r - m);
st[ls(p)].add += st[p].add;
st[rs(p)].add += st[p].add;
st[p].add = 0;
}

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 += k * (nr - nl + 1);
st[p].add += k;
return ;
}
push_down(p, nl, nr);
int m = mid(nl, nr);
plus(ls(p), nl, m, cl, cr, k);
plus(rs(p), m + 1, nr, cl, cr, k);
push_up(p);
}
ll query(int p, int nl, int nr, int ql, int qr) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return st[p].v;
push_down(p, nl, nr);
int m = mid(nl, nr);
return query(ls(p), nl, m, ql, qr) + query(rs(p), m + 1, nr, ql, qr);
}

$\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
56
57
58
59
60
61
62
63
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; }
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);
}
}
inline void push_down(int p, int l, int r) {
int m = _mid(l, r);
_st[_ls(p)].v += _st[p].add * (m - l + 1);
_st[_rs(p)].v += _st[p].add * (r - m);
_st[_ls(p)].add += _st[p].add;
_st[_rs(p)].add += _st[p].add;
_st[p].add = 0;
}
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;
}
push_down(p, nl, nr);
int m = _mid(nl, nr);
_plus(_ls(p), nl, m, cl, cr, k);
_plus(_rs(p), m + 1, nr, cl, cr, k);
push_up(p);
}
T _query(int p, int nl, int nr, int ql, int qr) {
if (nr < ql || qr < nl) return 0;
if (ql <= nl && nr <= qr) return _st[p].v;
push_down(p, nl, nr);
int m = _mid(nl, nr);
return _query(_ls(p), nl, m, ql, qr) +
_query(_rs(p), m + 1, nr, ql, qr);
}

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); }
};
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证