实用数据结构(三)

这篇博文介绍一下线段树以及应用

线段树概论

SegTree01
SegTree02
SegTree03

线段树求区间和

CH4301

CH4301

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
const int maxn = 500000 + 2;
const int inf = maxn;
int n, m;
int A[maxn];

class SegTree {
public:
int l, r, dat;
int sum, lmax, rmax;
};

typedef SegTree Node;

SegTree t[maxn * 4];

void build(int p, int l, int r) {
t[p].l = l;
t[p].r = r;

if(l == r) {
t[p].dat = t[p].sum = t[p].lmax = t[p].rmax = A[l];
return;
}

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

t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
t[p].lmax = max(t[p << 1].lmax, t[p << 1].sum + t[p << 1 | 1].lmax);
t[p].rmax = max(t[p << 1 | 1].rmax, t[p << 1 | 1].sum + t[p << 1].rmax);
t[p].dat = max(max(t[p << 1].dat, t[p << 1 | 1].dat), t[p << 1].rmax + t[p << 1 | 1].lmax);
}

void change(int p, int x, int v) {
if(t[p].l == t[p].r) {
t[p].sum = t[p].dat = t[p].lmax = t[p].rmax = v;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) change(p << 1, x, v);
else change(p << 1 | 1, x, v);

t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
t[p].lmax = max(t[p << 1].lmax, t[p << 1].sum + t[p << 1 | 1].lmax);
t[p].rmax = max(t[p << 1 | 1].rmax, t[p << 1 | 1].sum + t[p << 1].rmax);
t[p].dat = max(max(t[p << 1].dat, t[p << 1 | 1].dat), t[p << 1].rmax + t[p << 1 | 1].lmax);
}

Node ask(int p, int x, int y) {
// ask [x, y] dat
if(x <= t[p].l && t[p].r <= y) return t[p];

Node nl, nr, ans;
nl.lmax = nl.rmax = nl.sum = nl.dat = nr.lmax = nr.rmax = nr.dat = nr.sum = -inf;
ans.sum = 0;

int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) {
nl = ask(p << 1, x, y);
ans.sum += nl.sum;
}
if(y > mid) {
nr = ask(p << 1 | 1, x, y);
ans.sum += nr.sum;
}

ans.dat = max(max(nl.dat, nr.dat), nl.rmax + nr.lmax);
ans.lmax = max(nl.lmax, nl.sum + nr.lmax);
ans.rmax = max(nr.rmax, nr.sum + nl.rmax);

if(x > mid) ans.lmax = max(ans.lmax, nr.lmax);
if(y <= mid) ans.rmax = max(ans.rmax, nl.rmax);

return ans;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
_rep(i, 1, n) 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 << ask(1, x, y).dat << endl;
}
if(op == 2) change(1, x, y);
}
}

线段树求区间和(有条件)

如果线段树求区间和加了一些条件
比如在区间和相同的时候, 要求[l, r], l尽量小, 如果还有多解, 要求r也尽量小
此类问题可以对线段树维护的信息进行调整

1
2
3
4
输入的时候就对sum[]前缀和预处理
lmax换成lx, 表示从左边开始, 能够扩展的最长前缀的下标
rmax换成rx, 表示从右边开始, 能够扩展的最长后缀的下标
dat表示当前这个[l, r]区间, 能够找到的最优连续子区间是pair<int, int> dat

LA3938

LA3938

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
#define lowbit(i) (i & (-i))

typedef pair<int, int> PII;
const int maxn = 500000 + 2;
llong sum[maxn];
int n, m;

void init() {
Set(sum, 0);
}

llong cal(const PII x) {
return sum[x.second] - sum[x.first - 1];
}

PII better(const PII& lhs, const PII& rhs) {
llong suml = cal(lhs), sumr = cal(rhs);
if(suml != sumr) return suml > sumr ? lhs : rhs;
return lhs < rhs ? lhs : rhs;
}


class SegTree {
public:
int l, r;

PII dat;
int lx, rx;
};

SegTree t[maxn * 4];
typedef SegTree Node;

Node combine(const Node& lhs, const Node& rhs) {
Node ret;
ret.l = lhs.l; ret.r = rhs.r;

ret.lx = better(PII(lhs.l, lhs.lx), PII(lhs.l, rhs.lx)).second;
ret.rx = better(PII(rhs.rx, rhs.r), PII(lhs.rx, rhs.r)).first;
// then ret.dat = cross
ret.dat = better(better(lhs.dat, rhs.dat), PII(lhs.rx, rhs.lx));

return ret;
}

void build(int p, int l, int r) {
t[p].l = l;
t[p].r = r;

if(l == r) {
t[p].lx = t[p].rx = l;
t[p].dat = PII(l, l);
return;
}

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

t[p].lx = better(PII(t[p << 1].l, t[p << 1].lx), PII(t[p << 1].l, t[p << 1 | 1].lx)).second;
t[p].rx = better(PII(t[p << 1 | 1].rx, t[p << 1 | 1].r), PII(t[p << 1].rx, t[p << 1 | 1].r)).first;
t[p].dat = better(better(t[p << 1].dat, t[p << 1 | 1].dat), PII(t[p << 1].rx, t[p << 1 | 1].lx));
}

Node ask(int p, int x, int y) {
if(x <= t[p].l && t[p].r <= y) return t[p];

int mid = (t[p].l + t[p].r) >> 1;
Node ans;

if(x <= mid && mid < y) {
// both left tree and right tree
ans = combine(ask(p << 1, x, y), ask(p << 1 | 1, x, y));
}
else if(x <= mid) {
// only left
ans = ask(p << 1, x, y);
}
else if(mid < y) {
ans = ask(p << 1 | 1, x, y);
}

return ans;
}

int main() {
freopen("input.txt", "r", stdin);
int kase = 1;
while (scanf("%d%d", &n, &m) != EOF) {
init();
_rep(i, 1, n) {
llong x;
scanf("%lld", &x);
sum[i] = sum[i - 1] + x;
}

build(1, 1, n);
printf("Case %d:\n", kase++);

_rep(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
PII res = ask(1, x, y).dat;
printf("%d %d\n", res.first, res.second);
}
}
}

线段树+树状数组处理区间增加问题

CH4302
CH4302
CH4302-2

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
const int maxn = 500000 + 10;
int n, m;

llong A[maxn], B[maxn];
llong fwick[maxn];

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

void add(int x, llong d) {
for(; x <= n; x += lowbit(x)) fwick[x] += d;
}

llong sum(int x) {
llong ret = 0;
for(; x > 0; x -= lowbit(x)) ret += fwick[x];
return ret;
}

void init() {
Set(A, 0);
Set(B, 0);
Set(fwick, 0);
}

class SegTree {
public:
int l, r;
llong dat;
};

SegTree t[maxn * 4];
typedef SegTree Node;

void build(int p, int l, int r) {
t[p].l = l; t[p].r = r;
if(l == r) {
t[p].dat = B[l];
return;
}

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

t[p].dat = gcd(t[p << 1].dat, t[p << 1 | 1].dat);
}

void change(int p, int x, llong v) {
if(t[p].l == t[p].r) {
t[p].dat += v;
return;
}

int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) change(p << 1, x, v);
else change(p << 1 | 1, x, v);

t[p].dat = gcd(t[p << 1].dat, t[p << 1 | 1].dat);
}

llong ask(int p, int l, int r) {
if(l <= t[p].l && t[p].r <= r) {
return abs(t[p].dat);
}

int mid = (t[p].l + t[p].r) >> 1;

llong ret = 0;

if(l <= mid) ret = gcd(ret, ask(p << 1, l, r));
if(r > mid) ret = gcd(ret, ask(p << 1 | 1, l, r));

return abs(ret);
}

int main() {
freopen("input.txt", "r", stdin);
init();
scanf("%d%d", &n, &m);

_rep(i, 1, n) {
scanf("%lld", &A[i]);
B[i] = A[i] - A[i - 1];
}

// then build segTree
build(1, 1, n);

_for(i, 0, m) {
// query
char str[2];
scanf("%s", str);
int l, r;
scanf("%d%d", &l, &r);

if(str[0] == 'Q') {
//
llong al = A[l] + sum(l);
llong val = l < r ? ask(1, l + 1, r) : 0;
printf("%lld\n", gcd(al, val));
}

if(str[0] == 'C') {
//
llong d;
scanf("%lld", &d);
change(1, l, d);
if(r < n) change(1, r + 1, -d);

add(l, d);
add(r + 1, -d);
}
}
}