李超树详解
最近写了几棵李超树，算是线段树的扩展应用吧，顺便在这里讲讲。
概念：
李超树是一种高效的维护线段，单点查询端点最大值的一种线段树。支持插入一条线段，单点查询这个点的权值最大值（即包含这个点中所有线段的\(y\)的最大值）。
具体实现：
我们先将每一条线段都表示成点斜式，接下来用\(k\)表示斜率，\(b\)表示截距。当我们插入一条线段\(y = k x + b\)的到区间\([l,r]\)（插入直线则是\([-inf,inf]\)）时候，我们需要判断这条线段是否可以更新这个这个区间的答案。我们记一条线段\(s\)为优势线段，表示在这个区间\([l, r]\)中的线段中，\(s\)在\(mid = (l + r) >> 1\)这个点上的\(y\)的值是最大的。那么插入一条线段的时候，就会出现下面几种情况：
当这个区间还没有优势线段的时候，就可以直接将该线段设成该区间的优势线段，然后返回。当这个区间已经有优势线段，如果插入线段在区间
\([l, r]\)的值都比该优势线段大，那么就可以直接替换掉这个优势线段，然后返回。或者是在区间
\([l, r]\)的都比该优势线段小，那么就可以直接返回了。当这个区间的优势线段
\(seg\)和插入线段
\(s\)存在某个交点的时候，显然，我们需要更新这个区间的子区间的优势线段的答案。我们假设交点位置为
\(pos\)，该区间中点位置为
\(mid\)，
\(y_{seg_l} , y_{seg_r}\)表示
\(seg\)线段左右两个端点的
\(y\)值，
\(y_{s_l}, y_{s_r}\)同理。如果
\(y_{seg_l} < y_{s_l},y_{seg_r}>y_{s_r}\)，那么说明在
\(pos\)右边为
\(seg\)优，
\(pos\)左边为
\(s\)优，然后判断此时
\(pos\)的位置，如果此时
\(pos\)的位置在
\(mid\)的左边，说明
\(s\)这条优势线段仍然需要下方到子区间去，然后继续递归下去即可，另一半也是类似的。最后不要忘记更改本区间的优势线段就行了。
查询的话就比较简单了，像普通的线段树一样，如果当前区间在查询区间当中的话，那么就直接返回当前优势线段，否则递归处理，然后顺便和当前区间优势线段的\(y_{seg_{pos}}\)比较一下，返回值更加大的线段就行了。
复杂度证明：
查询操作不用多讲，是\(O(log(n))\)的，然后具体的就是插入的操作会达到\(O(log^2(n))\)。因为寻找需要插入的区间需要\(log(n)\)，然后一个区间的标记下方也需要\(O(log(n))\)的时间，所以总的复杂度也是\(O(nlog^2(n))\)的。
例题（SDOI2016 游戏）
题目传送门 大意：给出一个\(n\)个节点带边权的树，每个节点初始有一个值\(inf\)，要求支持这些操作： 1. 选择一条路径\(s, t\)，给路径上的每个点\(u\)加上\(dis[s][u] * a + b\)的数字。 2. 选择一条路径\(s, t\)，询问路径中所有数字的最小值。
题解： 维护路径就不用说了，直接上树剖就行了。我们将路径分成\(s \to Lca\)和\(Lca \to t\)两条路径，发现每个点加上的数字实际上是一条直线，然后我们就可以用李超树来维护这些直线了。总复杂度为\(O(nlog^3(n))\)的，信仰就行了。似乎用全局平衡二叉树就可以优化成\(O(nlog^2(n))\)了？不过那都是树剖的事了……
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 500;
const long long inf = 123456789123456789;
typedef long long ll;
int n, m, tot, clck;
int head[N], dfn[N], fa[N], top[N], idx[N], pos[N], heav[N], sz[N], dep[N], hav[N << 2];
ll dis[N], res[N << 2];
#define ls(o) (o << 1)
#define rs(o) (o << 1 | 1)
void read(int &x) {
x = 0;int f = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f;
}
void read(ll &x) {
x = 0;int f = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f;
}
struct edge {
int to, nxt, w;
}E[N << 2];
struct seg {
ll k, b;
ll F(ll x) {
return k * x + b;
}
void Print() {
cerr << k << " " << b << endl;
}
};
seg s[N << 2];
void Addedge(int u, int v, int w) {
E[++tot].to = v; E[tot].nxt = head[u]; head[u] = tot; E[tot].w = w;
E[++tot].to = u; E[tot].nxt = head[v]; head[v] = tot; E[tot].w = w;
}
void Dfs1(int o, int f, int deep, ll Dis) {
fa[o] = f; sz[o] = 1; dep[o] = deep; dis[o] = Dis;
int Mx = -1;
for(int i = head[o]; ~i; i = E[i].nxt) {
int to = E[i].to;
if(to == f) continue;
Dfs1(to, o, deep + 1, Dis + E[i].w);
sz[o] += sz[to];
if(sz[to] > Mx) {
Mx = sz[to];
heav[o] = to;
}
}
}
void Dfs2(int o, int tp) {
top[o] = tp; pos[dfn[o] = ++clck] = o;
if(!heav[o]) return ;
Dfs2(heav[o], tp);
for(int i = head[o]; ~i; i = E[i].nxt) {
int to = E[i].to;
if(!dfn[to]) Dfs2(to, to);
}
}
int GetLca(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
return y;
}
void Update(int o) {
res[o] = min(res[o], min(res[ls(o)], res[rs(o)]));
}
void Change(int o, int l, int r, seg nw) {
if(!hav[o]) return (void) (hav[o] = 1, s[o] = nw);
ll l1 = nw.F(dis[pos[l]]), r1 = nw.F(dis[pos[r]]), l2 = s[o].F(dis[pos[l]]), r2 = s[o].F(dis[pos[r]]);
if(l1 >= l2 && r1 >= r2) return ;
if(l2 >= l1 && r2 >= r1) return (void) (s[o] = nw, res[o] = min(res[o], min(l1, r1)));
int mid = (l + r) >> 1;
double pos0 = (double)(nw.b - s[o].b) / (double)(s[o].k - nw.k);
double mddis = (double)dis[pos[mid]];
if(pos0 <= mddis) Change(ls(o), l, mid, r2 >= r1 ? s[o] : nw);
else Change(rs(o), mid + 1, r, l2 >= l1 ? s[o] : nw);
if((pos0 <= mddis && r2 >= r1) || (pos0 > mddis && l2 >= l1)) s[o] = nw;
res[o] = min(res[o], min(l1, r1));
}
void Insert(int o, int L, int R, int l, int r, seg nw) {
if(l <= L && R <= r) return (void) (Change(o, L, R, nw));
int Mid = (L + R) >> 1;
if(Mid >= l) Insert(ls(o), L, Mid, l, r, nw);
if(Mid < r) Insert(rs(o), Mid + 1, R, l, r, nw);
Update(o);
}
ll Query(int o, int L, int R, int l, int r) {
if(l <= L && R <= r) return res[o];
ll ans = inf;
if(hav[o]) {
ll ret = min(s[o].F(dis[pos[max(l, L)]]), s[o].F(dis[pos[min(r, R)]]));
ans = min(ans, ret);
}
int Mid = (L + R) >> 1;
if(Mid >= l) ans = min(ans, Query(ls(o), L, Mid, l, r));
if(Mid < r) ans = min(ans, Query(rs(o), Mid + 1, R, l, r));
return ans;
}
void Modify(int x, int y, seg nw) {
while(top[x] != top[y]) {
Insert(1, 1, n, dfn[top[x]], dfn[x], nw);
x = fa[top[x]];
}
Insert(1, 1, n, dfn[y], dfn[x], nw);
}
ll Ask(int x, int y) {
ll ans = inf;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
ans = min(ans, Query(1, 1, n, dfn[top[x]], dfn[x]));
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
ans = min(ans, Query(1, 1, n, dfn[y], dfn[x]));
return ans;
}
int main() {
memset(head, -1, sizeof head);
read(n); read(m);
for(int i = 1, u, v, w; i < n; i++) {
read(u); read(v); read(w);
Addedge(u, v, w);
}
Dfs1(1, 0, 1, 0); Dfs2(1, 1);
seg Inf = (seg) {0, inf};
for(int i = 1; i <= n * 4; i++) res[i] = inf, s[i] = Inf, hav[i] = 1;
for(int i = 1, tp; i <= m; i++) {
read(tp);
if(tp == 1) {
int s, t;
ll a, b;
read(s); read(t); read(a); read(b);
int Lca = GetLca(s, t);
seg S1 = (seg) {-a, b + (ll)dis[s] * a};
seg S2 = (seg) {a, b + (ll)(dis[s] - 2 * dis[Lca]) * a};
Modify(s, Lca, S1);
Modify(t, Lca, S2);
}
else {
int s, t;
read(s); read(t);
printf("%lld\n", Ask(s, t));
}
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10507460.html
相关资源：JAVA上百实例源码以及开源项目
