主席树
洛谷 P3834 【模板】可持久化线段树 1（主席树，离散化）
既然是主席树的模板题，就大概说一说主席树。
题目的要求是求给定的区间第k大元素，首先如果这道题不是给定区间[L,R]，而是求一棵权值线段树上的第k大，这个的求法是什么，这样就比较容易了，就是这个题HDU2852 KiKi's K-Number(值域线段树,求线段树第k大)，在线段树上叶子节点表示这个节点的值出现了几次，然后就像普通的线段树一样更新上去，要查找第k大的时候，就从根节点出发先看左子树的节点数x是否大于等于k，如果大于等于k就向左子树找，如果小于k,就去右子树找，去右子树找的时候k就变成了x-k，最后就可以找到第k大的位置。
主席树是什么，主席树也被称做可持久化线段树，它采取动态建树的方式建了一个有n个节点的线段树，由于是动态开点，动态建树，所以复杂度是$O(nlgn)$，建立方法是首先建立一棵空树，然后依次把给出序列的值插入这棵空树，每插入一个值，就新开一个根节点建立线段树，第i个线段树存储的信息是区间[1,i]的信息，所以面对询问求[l,r]的第k大，我们就可以转化成sum[r]-sum[l-1]类似前缀和相减的方式来把[1,r]和[1,l-1]这两棵线段树进行相减，然后求第k大的时候也是边递归边求第k大。
详细的讲解请参考这个博客:主席树详解
代码
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int node_cnt, n, m;
int sum[N << 5], rt[N], lc[N << 5], rc[N << 5];
int a[N], b[N], p; //原序列和离散序列和修改点
void build(int &t, int l, int r)
{
t = ++node_cnt;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lc[t], l, mid);
build(rc[t], mid + 1, r);
}
int modify(int o, int l, int r)
{
int oo = ++node_cnt;
lc[oo] = lc[o];
rc[oo] = rc[o];
sum[oo] = sum[o] + 1;
if (l == r)
return oo;
int mid = (l + r) >> 1;
if (p <= mid)
lc[oo] = modify(lc[oo], l, mid);
else
rc[oo] = modify(rc[oo], mid + 1, r);
return oo;
}
int query(int u, int v, int l, int r, int k) //求u,v这两棵线段树的差的树中的第k大
{
int mid = (l + r) >> 1, ans;
int x = sum[lc[v]] - sum[lc[u]];
if (l == r)
return l;
if (x >= k)
ans = query(lc[u], lc[v], l, mid, k);
else
ans = query(rc[u], rc[v], mid + 1, r, k - x);
return ans;
}
void init()
{
node_cnt = 0;
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int q = unique(b + 1, b + n + 1) - (b + 1);
build(rt[0], 1, q);
for (int i = 1; i <= n; i++)
{
p = lower_bound(b + 1, b + q + 1, a[i]) - b;
rt[i] = modify(rt[i - 1], 1, q);
}
int l, r, k;
while (m--)
{
scanf("%d%d%d", &l, &r, &k);
int ans = query(rt[l - 1], rt[r], 1, q, k);
printf("%d\n", b[ans]);
}
return 0;
}
LOJ2432「POI2014」代理商 Couriers(主席树)
因为数据并不大，所以这一题可以不用离散化，先建立一棵空树，然后构造主席树，对于每个询问[l,r]，先计算出k=(r-l+1)>>1的值，然后直接在主席树中查询，如果左子树的节点数大于k，就往左子树查，右子树大于k就往右子树查，否则为0。
int query(int u, int v, int l, int r, int k)
{
int mid = (l + r) >> 1, ans;
int x = sum[lc[v]] - sum[lc[u]];
int y = sum[rc[v]] - sum[rc[u]];
if (l == r)
return l;
if (x > k)
ans = query(lc[u], lc[v], l, mid, k);
else if (y > k)
ans = query(rc[u], rc[v], mid + 1, r, k);
else
ans = 0;
return ans;
}
void init()
{
node_cnt = 0;
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
init();
build(rt[0], 1, n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
p = a[i];
rt[i] = modify(rt[i - 1], 1, n);
}
int l, r;
while (m--)
{
scanf("%d%d", &l, &r);
int k = (r - l + 1) >> 1;
printf("%d\n", query(rt[l - 1], rt[r], 1, n, k));
}
return 0;
}
SPOJ COT - Count on a tree(树链剖分+LCA+主席树,树上第k大)
给你n个节点，每个节点对应有权值，然后给你n-1条边，使之形成一棵树,然后有m组询问，每次询问u v k,求从u点到v点的第k小值.
首先这是一棵树，不是区间，所以不能用主席树直接求出两点之间路径的第k大。本来想用树链剖分搞一搞，但是想到虽然剖分成了若干条链，但是这两个节点不一定在一条链上，所以我们要换一种思路。
我们可以用熟练剖分求助这两个点的lca，然后构建一棵主席树，但是这个主席树的构建方法和之间构造区间不一样，之前的区间构造方法是[1,i]前缀和的形式构造，那么对于这个题我们可以对每一个节点到根节点建立前缀和,就能找任意个节点到根节点的第K值,
那么根据主席树的性质,我们就能够计算(u,v)的路上的第K值了
考虑对于任意两个点$u,v$,现在已经构造出了一棵主席树，前缀和存储的是根节点到该节点，那么我们我们就把从根节点到u和从根节点到v的路径加起来，这个过程肯定存在重复计算，我们要把重复的路径减去，重复的路径是从根节点到lca对应的线段树,但是我们要保留其中一个lca，所以就是计算出:
sum[u]+sum[v]-sum[lca]-sum[fa[lca]]
这一棵线段树的第k大，直接求出就好
代码
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
int fa[N], dep[N], siz[N], son[N], top[N], w[N];
int first[N], tot;
int b[N], p;
int sum[N << 5], rt[N], lc[N << 5], rc[N << 5], node_cnt;
struct edge
{
int v, next;
} e[N * 2];
void init()
{
mem(first, -1);
tot = 0;
node_cnt = 0;
}
void add_edge(int u, int v)
{
e[tot].v = v;
e[tot].next = first[u];
first[u] = tot++;
}
int qlca(int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
void build(int &t, int l, int r)
{
t = ++node_cnt;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lc[t], l, mid);
build(rc[t], mid + 1, r);
}
int modify(int o, int l, int r)
{
int oo = ++node_cnt;
lc[oo] = lc[o];
rc[oo] = rc[o];
sum[oo] = sum[o] + 1;
if (l == r)
return oo;
int mid = (l + r) >> 1;
if (p <= mid)
lc[oo] = modify(lc[oo], l, mid);
else
rc[oo] = modify(rc[oo], mid + 1, r);
return oo;
}
int query(int u, int v, int lca, int flca, int l, int r, int k)
{
int mid = (l + r) >> 1, ans;
int x = sum[lc[u]] + sum[lc[v]] - sum[lc[lca]] - sum[lc[flca]];
if (l == r)
return b[l];
if (x >= k)
ans = query(lc[u], lc[v], lc[lca], lc[flca], l, mid, k);
else
ans = query(rc[u], rc[v], rc[lca], rc[flca], mid + 1, r, k - x);
return ans;
}
void dfs1(int u, int f, int deep)
{
fa[u] = f;
dep[u] = deep;
siz[u] = 1;
son[u] = 0;
int maxson = -1;
for (int i = first[u]; ~i; i = e[i].next)
{
int v = e[i].v;
if (v == f)
continue;
dfs1(v, u, deep + 1);
siz[u] += siz[v];
if (siz[v] > maxson)
{
son[u] = v;
maxson = siz[v];
}
}
}
int q;
void dfs2(int u, int topf)
{
top[u] = topf;
p = w[u]; //在这个地方建立主席树
rt[u] = modify(rt[fa[u]], 1, q);
if (!son[u])
return;
dfs2(son[u], topf);
for (int i = first[u]; ~i; i = e[i].next)
{
int v = e[i].v;
if (v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
}
int main()
{
// freopen("in.txt", "r", stdin);
int u, v, k;
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
b[i] = w[i];
}
sort(b + 1, b + n + 1);
for (int i = 1; i <= n - 1; i++)
{
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
q = unique(b + 1, b + n + 1) - (b + 1);
//计算出新的节点的标号
for (int i = 1; i <= n; i++)
w[i] = lower_bound(b + 1, b + q + 1, w[i]) - b;
build(rt[0], 1, q);
dfs1(1, 0, 1);
dfs2(1, 1);
while (m--)
{
scanf("%d%d%d", &u, &v, &k);
int lca = qlca(u, v);
int flca = fa[lca];
int ans = query(rt[u], rt[v], rt[lca], rt[flca], 1, q, k);
printf("%d\n", ans);
}
return 0;
}
洛谷 P2617 Dynamic Rankings(主席树套树状数组,动态Kth)
这道题在普通的主席树上求第k大上面，增加了单点修改的需求.
因为主席树是离线数据结构，这样就导致了单点修改比较麻烦，所以我们可以利用树状数组来维护区间和,主席树的作用是维护位置.
但是因为主席树是离线数据结构，我们需要对所有的查询离线处理，先把所有可能出现的节点信息保存下来，然后再去重离散化，
我们现在建出来的主席树，第i个根维护的是$[i-lowbit(i)+1,i]$区间的信息，而不是像以前的前缀树一样。
#define mem(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;
int rt[N << 5], rc[N << 5], lc[N << 5];
int a[N], b[N], node_cnt, sum[N << 5], q;
int cl[N], cr[N], ck[N], xx[N], yy[N];
int n, m, totx, toty;
void init()
{
node_cnt = 0;
q = 0;
}
int lowbit(int x)
{
return x & -x;
}
void update(int &o, int l, int r, int x, int p, int v)
{
o = ++node_cnt;
sum[o] = sum[x] + v;
lc[o] = lc[x];
rc[o] = rc[x];
if (l == r)
return;
int mid = (l + r) >> 1;
if (p <= mid)
update(lc[o], l, mid, lc[x], p, v);
else
update(rc[o], mid + 1, r, rc[x], p, v);
}
int query(int l, int r, int k)
{
int mid = (l + r) >> 1;
if (l == r)
return l;
int x = 0;
//求r到l-1的前缀和
for (int i = 1; i <= totx; i++)
x -= sum[lc[xx[i]]];
for (int i = 1; i <= toty; i++)
x += sum[lc[yy[i]]];
if (x >= k)
{
for (int i = 1; i <= totx; i++)
xx[i] = lc[xx[i]];
for (int i = 1; i <= toty; i++)
yy[i] = lc[yy[i]];
return query(l, mid, k);
}
else
{
for (int i = 1; i <= totx; i++)
xx[i] = rc[xx[i]];
for (int i = 1; i <= toty; i++)
yy[i] = rc[yy[i]];
return query(mid + 1, r, k - x);
}
}
void add(int x, int v)
{
int k = lower_bound(b + 1, b + q + 1, a[x]) - b;
for (int i = x; i <= n; i += lowbit(i))
update(rt[i], 1, q, rt[i], k, v);
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[++q] = a[i];
}
char s[5];
for (int i = 1; i <= m; i++)
{
scanf("%s", s);
if (s[0] == 'Q')
scanf("%d%d%d", &cl[i], &cr[i], &ck[i]);
else if (s[0] == 'C')
{
scanf("%d%d", &cl[i], &cr[i]);
b[++q] = cr[i];
}
}
sort(b + 1, b + q + 1);
q = unique(b + 1, b + q + 1) - (b + 1);
for (int i = 1; i <= n; i++)
add(i, 1);
for (int i = 1; i <= m; i++)
{
if (ck[i])
{
totx = toty = 0;
for (int j = cl[i] - 1; j; j -= lowbit(j)) //l-1
xx[++totx] = rt[j];
for (int j = cr[i]; j; j -= lowbit(j)) //r
yy[++toty] = rt[j];
printf("%d\n", b[query(1, q, ck[i])]);
}
else
{
//单点更新操作
add(cl[i], -1);
a[cl[i]] = cr[i];
add(cl[i], 1);
}
}
return 0;
}