acwing算法提高之数据结构--线段树

1 介绍

线段树是算法竞赛中常用的用来维护区间信息的数据结构。

线段树可以在O(logN)时间复杂度内完成以下操作：

单点修改。
区间修改（需要加入懒标记）。
区间查询（区间求和、求区间最大值、求区间最小值）。

2 训练

题目1：1275最大数

C++代码如下，
涉及到单点修改、区间查询最大值这两个操作。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long LL;const int N = 2000010;int m, p;
struct Node {int l, r;int v; //区间[l,r]中的最大值
} tr[N * 4];void pushup(int u) {//由子结点信息，更新父结点信息tr[u].v = max(tr[u * 2].v, tr[u * 2 + 1].v);
}void build(int u, int l, int r) { //建立线段树tr[u] = {l, r};if (l == r) return;int mid = l + r >> 1;build(2 * u, l, mid), build(2 * u + 1, mid + 1, r);
}int query(int u, int l, int r) {//查询区间[l,r]最大值if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1;int v = 0;if (l <= mid) v = query(2 * u, l, r);if (r > mid) v = max(v, query(2 * u + 1, l, r));return v;
}void modify(int u, int x, int v) { //单点修改:将a[x]修改为v,线段树tr[u]需要进行的操作if (tr[u].l == x && tr[u].r == x) tr[u].v = v;else {int mid = tr[u].l + tr[u].r >> 1;if (x <= mid) modify(2 * u, x, v);else modify(2 * u + 1, x, v);pushup(u);}
}int main() {int n = 0, last = 0;cin >> m >> p;build(1, 1, m);int x;string op;while (m--) {cin >> op >> x;if (op == "Q") {last = query(1, n - x + 1, n);cout << last << endl;} else {modify(1, n + 1, ((LL)last + x) % p);n++;}}return 0;
}

题目2：245你能回答这些问题吗

C++代码如下，
涉及到单点修改、求区间的最大连续子数组和这两个操作。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 500010;int n, m;
int w[N];
struct Node {int l, r;int sum, lmax, rmax, tmax;
}tr[N * 4];void pushup(Node &u, Node &l, Node &r) {u.sum = l.sum + r.sum;u.lmax = max(l.lmax, l.sum + r.lmax);u.rmax = max(r.rmax, r.sum + l.rmax);u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}void pushup(int u) {pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}void build(int u, int l, int r) {if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};else {tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(int u, int x, int v) {if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};else {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);}
}Node query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u];else {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 {auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);Node res;pushup(res, left, right);return res;}}
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);build(1, 1, n);int k, x, y;while (m--) {scanf("%d%d%d", &k, &x, &y);if (k == 1) {if (x > y) swap(x, y);printf("%d\n", query(1, x, y).tmax);} else {modify(1, x, y);}}return 0;
}

题目3：246区间最大公约数

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 500010;int n, m;
LL w[N];
struct Node {int l, r;LL sum, d;
}tr[N * 4];LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}void pushup(Node &u, Node &l, Node &r) {u.sum = l.sum + r.sum;u.d = gcd(l.d, r.d);
} void pushup(int u) {pushup(tr[u], tr[u<<1], tr[u << 1 | 1]);
}void build(int u, int l, int r) {if (l == r) {LL b = w[r] - w[r-1];tr[u] = {l, r, b, b};} else {tr[u].l = l, tr[u].r = r;int mid = l + r >> 1;build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(int u, int x, LL v) {if (tr[u].l == x && tr[u].r == x) {LL b = tr[u].sum + v;tr[u] = {x, x, b, b};} else {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);}
}Node query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u];else {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 {auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);Node res;pushup(res, left, right);return res;}}
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%lld", &w[i]);build(1, 1, n);int l, r;LL d;char op[2];while (m--) {scanf("%s%d%d", op, &l, &r);if (*op == 'Q') {auto left = query(1, 1, l);Node right({0, 0, 0, 0});if (l + 1 <= r) right = query(1, l + 1, r);printf("%lld\n", abs(gcd(left.sum, right.d)));} else {scanf("%lld", &d);modify(1, l, d);if (r + 1 <= n) modify(1, r + 1, -d);}}return 0;
}

题目4：243一个简单的整数问题2

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, m;
int w[N];
struct Node {int l, r;LL sum, add;
}tr[N * 4];void pushup(int u) {tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}void pushdown(int u) {auto &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];if (root.add) {left.add += root.add, left.sum += (LL)(left.r - left.l + 1) * root.add;right.add += root.add, right.sum += (LL)(right.r - right.l + 1) * root.add;root.add = 0;}
}void build(int u, int l, int r) {if (l == r) tr[u] = {l, r, w[r], 0};else {tr[u] = {l, r};int mid = l + r >> 1;build(u<<1, l, mid), build(u<<1|1, mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int d) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;tr[u].add += d;} else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u<<1, l, r, d);if (r > mid) modify(u<<1|1, l, r, d);pushup(u);}
}LL query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL sum = 0;if (l <= mid) sum = query(u<<1, l, r);if (r > mid) sum += query(u<<1|1, l, r);return sum;
}int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);build(1, 1, n);char op[2];int l, r, d;while (m--) {scanf("%s%d%d", op, &l, &r);if (*op == 'C') {scanf("%d", &d);modify(1, l, r, d);} else printf("%lld\n", query(1, l, r));}return 0;
}

题目5：247亚特兰蒂斯

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 100010;int n;
struct Segment {double x, y1, y2;int k;bool operator< (const Segment &t) const {return x < t.x;}
}seg[N * 2];struct Node {int l, r;int cnt;double len;
}tr[N * 8];vector<double> ys;int find(double y) {return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}void pushup(int u) {if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];else if (tr[u].l != tr[u].r) {tr[u].len = tr[u<<1].len + tr[u<<1|1].len;}else tr[u].len = 0;
}void build(int u, int l, int r) {tr[u] = {l, r, 0, 0};if (l != r) {int mid = l + r >> 1;build(u<<1, l, mid), build(u<<1|1, mid+1, r);}
}void modify(int u, int l, int r, int k) {if (tr[u].l >= l && tr[u].r <= r) {tr[u].cnt += k;pushup(u);} else {int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u<<1, l, r, k);if (r > mid) modify(u<<1|1, l, r, k);pushup(u);}
}int main() {int T = 1;while (scanf("%d", &n), n) {ys.clear();for (int i = 0, j = 0; i < n; ++i) {double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);seg[j++] = {x1, y1, y2, 1};seg[j++] = {x2, y1, y2, -1};ys.push_back(y1), ys.push_back(y2);}sort(ys.begin(), ys.end());ys.erase(unique(ys.begin(), ys.end()), ys.end());build(1, 0, ys.size() - 2);sort(seg, seg + n * 2);double res = 0;for (int i = 0; i < n * 2; ++i) {if (i > 0) res += tr[1].len * (seg[i].x - seg[i-1].x);modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);}printf("Test case #%d\n", T++);printf("Total explored area: %.2lf\n\n", res);}return 0;
}

题目6：1277维护序列

C++代码如下，

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n, p, m;
int w[N];
struct Node {int l, r;int sum, add, mul;
}tr[N * 4];void pushup(int u) {tr[u].sum = (tr[u<<1].sum + tr[u<<1|1].sum) % p;
}void eval(Node &t, int add, int mul) {t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p;t.mul = (LL)t.mul * mul % p;t.add = ((LL)t.add * mul + add) % p;
}void pushdown(int u) {eval(tr[u<<1], tr[u].add, tr[u].mul);eval(tr[u<<1|1], tr[u].add, tr[u].mul);tr[u].add = 0, tr[u].mul = 1;
}void build(int u, int l, int r) {if (l == r) tr[u] = {l, r, w[r], 0, 1};else {tr[u] = {l, r, 0, 0, 1};int mid = l + r >> 1;build(u<<1, l, mid), build(u<<1|1, mid + 1, r);pushup(u);}
}void modify(int u, int l, int r, int add, int mul) {if (tr[u].l >= l && tr[u].r <= r) eval(tr[u], add, mul);else {pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u<<1, l, r, add, mul);if (r > mid) modify(u<<1|1, l, r, add, mul);pushup(u);}
}int query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;int sum = 0;if (l <= mid) sum = query(u<<1, l, r);if (r > mid) sum = (sum + query(u<<1|1, l, r)) % p;return sum;
}int main() {scanf("%d%d", &n, &p);for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);build(1, 1, n);scanf("%d", &m);while (m--) {int t, l, r, d;scanf("%d%d%d", &t, &l, &r);if (t == 1) {scanf("%d", &d);modify(1, l, r, 0, d);} else if (t == 2) {scanf("%d", &d);modify(1, l, r, d, 1);} else printf("%d\n", query(1, l, r));}return 0;
}