- // 区间更新求和
- inline int ls(int p) { return p <<1; }// 左儿子
- inline int rs(int p) { return p << 1 | 1; }// 右儿子
- void push_up(int p) {
- t[p] = t[ls(p)] + t[rs(p)];
- }// 向上不断维护区间操作
- void build(ll p, ll l, ll r) {
- if (l == r) { t[p] = a[l]; return; }
- ll mid = (l + r)>> 1;
- build(ls(p), l, mid);
- build(rs(p), mid + 1, r);
- push_up(p);
- }
- inline void f(ll p, ll l, ll r, ll k) {
- tag[p] = tag[p] + k;
- t[p] = t[p] + k * (r - l + 1);
- }
- inline 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;
- }
- inline void update(ll ul, ll ur, ll l, ll r, ll p, ll k) {
- //ul,ur 为要修改的区间
- //l,r,p 为当前节点所存储的区间以及节点的编号
- if (ul <= l && r <= ur) {
- t[p] += k * (r - l + 1);
- tag[p] += k;
- return;
- }
- push_down(p, l, r);
- ll mid = (l + r)>> 1;
- if (ul <= mid)update(ul, ur, l, mid, ls(p), k);
- if (ur>mid) update(ul, ur, mid + 1, r, rs(p), k);
- push_up(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;
- }
解决问题类型:
区间 rmq 即其他符合结合律的运算, 支持区间更新.
想法题
[二分] 找第 k 个 0: 结点维护 0 的个数 cnt[rt], 然后在树上队 cnt 二分.
[二分] 找第 k 大(权值线段树): 这个问题可以排序或 nth_element(start,start+first,start+last).
考虑线段树的做法, 我们先将 n 个数离散化到 [1,n] 范围. 建一个 1~n 的空树, 每个结点维护 tot 即该区间有几个数. 然后将 n 个数字依次插入:
- void insert(int x,int root = 1)
- {
- if(seg[root].l == seg[root].r)
- {
- set[root].tot++;
- return ;
- }
- int mid = seg[root].l + seg[root].r>> 1;
- if(x <= mid)// 在左儿子当中
- insert(k,lson);
- if(x> mid)// 在右儿子当中
- insert(k,rson);
- //Push up the information
- }
查找:
- int query(int k,int root = 1)
- {
- if(seg[root].l == seg[root].r)
- return seg[root].l;// 找到了
- int mid = seg[lson].tot;// 左儿子区间的数字个数
- if(k <= mid)
- return query(k,lson);// 左儿子里面找
- else if(k> mid)
- return query(k - mid,rson);// 右儿子里面找
- }
这就是权值线段树, 所有叶子节点相当于一个统计每个数出现次数的 cnt 数组, 然后再把这些信息求和地 push_up
[二分] 给定 x, 找最小的 i 使得 \(prefixSum[i]>x\): 树上二分即可.
[dp] 找最大子段和. 你可以 dp O(n)做, 也可以线段树维护四个值: 区间和, 区间最大子段和, 最大前缀, 最大后缀.
push_up 这么写(dp 的感觉).
- struct data {
- int sum, pref, suff, ans;
- };
- data combine(data l, data r) {
- data res;
- res.sum = l.sum + r.sum;
- res.pref = max(l.pref, l.sum + r.pref);
- res.suff = max(r.suff, r.sum + l.suff);
- res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
- return res;
- }
[树套数据结构] 无序区间 lower_bound(): 每个结点存该区间的有序序列.\(O(n \log n)\)空间
- vector<int> t[4*MAXN];
- //O(n log n)建树
- void build(int a[], int v, int tl, int tr) {
- if (tl == tr) {
- t[v] = vector<int>(1, a[tl]);
- } else {
- int tm = (tl + tr) / 2;
- build(a, v*2, tl, tm);
- build(a, v*2+1, tm+1, tr);
- merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
- back_inserter(t[v]));
- }
- }
- //O(log^2n)询问
- int query(int v, int tl, int tr, int l, int r, int x) {
- if (l> r)
- return INF;
- if (l == tl && r == tr) {
- vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
- if (pos != t[v].end())
- return *pos;
- return INF;
- }
- int tm = (tl + tr) / 2;
- return min(query(v*2, tl, tm, l, min(r, tm), x),
- query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
- }
- // 若想单点更新, 每个结点存 multiset 建树时空花费为 O(nlog^2n)
- void update(int v, int tl, int tr, int pos, int new_val) {
- t[v].erase(t[v].find(a[pos]));
- t[v].insert(new_val);
- if (tl != tr) {
- int tm = (tl + tr) / 2;
- if (pos <= tm)
- update(v*2, tl, tm, pos, new_val);
- else
- update(v*2+1, tm+1, tr, pos, new_val);
- } else {
- a[pos] = new_val;
- }
- }
[fractional cascading] 把上一个问题优化为 \(O(\log n)\).
考虑子问题: 有 n 个数, 被分成 k 个有序序列, 分别对每个序列询问 lower_bound, 如何将 \(O(klog\frac{n}{k})\) 优化为 \(O(logn)\)?
一个想法是对每个数预处理它在其它 k-1 个序列中 lower_bound 的结果(假装没有时间花费吧, 暂时想不出有什么好办法.). 这样直接对合并的序列直接二分, 然后查预处理的表即可. 不过空间花费为 O(kn)
如何优化为 O(n)??? 看不懂...
[二维] 单点修改, 询问某个子矩阵最大值. 先对 x 坐标建树 tree_x, 对它的每个结点都建一个线段树 tree_y
- // 空间 O(16nm)
- void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
- if (ly == ry) {
- if (lx == rx)
- t[vx][vy] = a[lx][ly];
- else
- t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
- } else {
- int my = (ly + ry) / 2;
- build_y(vx, lx, rx, vy*2, ly, my);
- build_y(vx, lx, rx, vy*2+1, my+1, ry);
- t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
- }
- }
- void build_x(int vx, int lx, int rx) {
- if (lx != rx) {
- int mx = (lx + rx) / 2;
- build_x(vx*2, lx, mx);
- build_x(vx*2+1, mx+1, rx);
- }
- build_y(vx, lx, rx, 1, 0, m-1);
- }
- int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
- if (ly> ry)
- return 0;
- if (ly == tly && try_ == ry)
- return t[vx][vy];
- int tmy = (tly + try_) / 2;
- return sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
- + sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry);
- }
- int sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
- if (lx> rx)
- return 0;
- if (lx == tlx && trx == rx)
- return sum_y(vx, 1, 0, m-1, ly, ry);
- int tmx = (tlx + trx) / 2;
- return sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
- + sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry);
- }
- void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
- if (ly == ry) {
- if (lx == rx)
- t[vx][vy] = new_val;
- else
- t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
- } else {
- int my = (ly + ry) / 2;
- if (y <= my)
- update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
- else
- update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
- t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
- }
- }
- void update_x(int vx, int lx, int rx, int x, int y, int new_val) {
- if (lx != rx) {
- int mx = (lx + rx) / 2;
- if (x <= mx)
- update_x(vx*2, lx, mx, x, y, new_val);
- else
- update_x(vx*2+1, mx+1, rx, x, y, new_val);
- }
- update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
- }
[二维] 如果给出 n 个坐标, 询问矩阵里有几个坐标, 我们可以将空间优化到 \(O(n \log n)\).
具体来说, 对于某个 tree_x 上的结点, 如果它的区间是 \([l,r]\), 那么我们只用这个区间的点建树
[主席树] 每次更新前都存一次历史版本 (Git-hub??). 考虑到线段树每次更新的部分很少(O(logn) 长的链)所以每次只是创建一个新的链, 然后把它连到上一个版本上. 这样就要用到指针.
- // 单点更新, 区间求和的可持续化线段树
- struct Vertex {
- Vertex *l, *r;
- int sum;
- Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
- Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
- if (l) sum += l->sum;
- if (r) sum += r->sum;
- }
- };
- Vertex* build(int a[], int tl, int tr) {
- if (tl == tr)
- return new Vertex(a[tl]);
- int tm = (tl + tr) / 2;
- return new Vertex(build(a, tl, tm), build(a, tm+1, tr));
- }
- int get_sum(Vertex* v, int tl, int tr, int l, int r) {
- if (l> r)
- return 0;
- if (l == tl && tr == r)
- return v->sum;
- int tm = (tl + tr) / 2;
- return get_sum(v->l, tl, tm, l, min(r, tm))
- + get_sum(v->r, tm+1, tr, max(l, tm+1), r);
- }
- Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
- if (tl == tr)
- return new Vertex(new_val);
- int tm = (tl + tr) / 2;
- if (pos <= tm)
- return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
- else
- return new Vertex(v->l, update(v->r, tm+1, tr, pos, new_val));
- }
[主席树] 区间第 k 大:
? 0. 将问题化简为 \(0 \le a[i] \lt n\) , 知求前缀的第 k 大.
? 1. 前缀第 k 大可以用权值线段树解决. 于是我们可持久化地建 n 颗树.
2. 对于 a[i]取值任意的, 用离散化变成 \(0 \le a[i] \lt n\)
? 3. 对于任意区间, 我们在树上二分时将 tot[x]变为第 l 颗减第 r-1 颗的即可.
复杂度:
\(o(nlogn)\)
例题
A - Who has a better strategy ? https://vjudge.net/problem/Gym-102035F :
暂时超出理解范围
用怪的强度作为下标, 维护两个人打怪的时间, 在线段树上二分找答案即可.
C - Super Mario https://vjudge.net/problem/HDU-4417
区间小于 x 的有几个数.
略
B - 永无乡 https://vjudge.net/problem/HYSBZ-2733
线段树合并模板题
D - To the moon https://vjudge.net/problem/HDU-4348
区间更新, 询问历史版本区间和, 回到历史版本.
标记永久化, 计算下每个标记的贡献即可.
E - Kth number https://vjudge.net/problem/HDU-2665
略
F - Count on a tree https://vjudge.net/problem/SPOJ-COT
询问树上两点之间的链第 k 大.
维护树上前缀, 和树上距离公式一样处理
G - D-query https://vjudge.net/problem/SPOJ-DQUERY
询问区间几个不同的树
可能有些人还不理解, 放一个离线版本的.
H - Query on A Tree https://vjudge.net/problem/HDU-6191
询问 x 异或子树 u 里的某个结点的最大值
可持久化字典树, 用 dfs 序就可以变成区间询问.
I - Army Formations https://vjudge.net/problem/HDU-6133
给出一棵树共 nn 个顶点, 每个顶点有一个权值 \(val_i\), 你需要对每个节点统计一个最优解
每个节点的解按照一定规则产生: 取出该节点的子树下所有的顶点, 把顶点任意排序成一个序列, 设为 \(v1,v2...,vk\)
此时解为 \(\sum_{i=1}^{k}\sum_{j=1}^{i}val_{v_j}\), 最小的解为最优解
线段树合并, 维护前缀和的前缀和. 维护每个区间前缀和的前缀和, 前缀和, 个数, 就可以向上合并, 叶子结点的计算就是等差数列求和.
J - Lovers https://vjudge.net/problem/HDU-6562
初始 n 个空串, m 个操作:
1. 给 [l,r] 的所有字符串头尾加一个'd', 将原字符串 x 变为 dxd
2. 求 [l,r] 所有字符串代表的数字之和 mod 1e9+7
更新操作时可以合并的. 合并两个操作, 只用维护那个数字正着和倒着的大小以及长度就可以. 快速更新一段区间, 也只用知道区间所有数字的 10 的长度次的和就可以了.
K - The Child and Sequence https://vjudge.net/problem/CodeForces-438D
给一个序列
支持 3 种操作
1 u v 对于所有 i u<=i<=v, 输出 a[i]的和
2 u v t 对于所有 i u<=i<=v a[i]=a[i]%t
3 u v 表示 a[u]=v(将 v 赋值给 a[u])
n,q<=1e5 a[i],t,v<=1e9
维护区间最值快速判断还有没有数字需要更新, 有的话, 暴力更新就好了.
代码
来源: http://www.bubuko.com/infodetail-3158693.html