可持久化线段树，也叫作函数式线段树，也就是主席树，（。。。因为先驱就是fotile主席。。Orz。。。）
网上的教程很少啊，有的教程写得特别简单，4行中文，然后就是一篇代码～～
这里，我将从查找区间第k小值（不带修改）题的可持久化线段树做法中，讲一讲主席树。
/*只是略懂，若有错误，还请多多包涵！*/
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。/*找不到比较科学的定义，就拿这个凑凑数吧～～～*/
这个数据结构很坑啊，我研究了一整天才差不多理解了一些（。。太笨了。。。）。所以，要理解好每一个域或变量的意义。
开讲！
一些数据结构，比如线段树或平衡树，他们一般是要么维护每个元素在原序列中的排列顺序，要么是维护每个元素的大小顺序，若是像二者兼得。。（反正我是觉得很。。）那么，这道题就想想主席树吧～/*还可以用划分树做*/
开讲！～好像说过一边了
既然叫“函数式线段树”，那么就应该有跟普通线段树相同的地方。一颗线段树，只能维护一段区间里的元素。但是，每个询问的区间都不一样，若是对每段区间都单独建立的线段树，那～萎定了～。因此，就要想，如何在少建，或建得快的情况下，能利用一些方法，得出某个区间里的情况。
比如一棵线段树，记为tree[i][j]，表示区间[i,j]的线段树。那么，要得到它的情况，可以利用另外两棵树，tree[1][i-1]和tree[1][j]，得出来。也就是说，可以由建树的一系列历史版本推出。
那么，怎么创建这些树呢？
首先，离散化数据。因为如果数据太大的话，线段树会爆～～
在所有树中，是按照当前区间元素的离散值（也就是用大小排序）储存的，在每个节点，存的是这个区间每个元素出现的次数之和（data域）。出现的次数，也就是存了多少数进来（建树时，是一个数一个数地存进来的）。
先建议棵线段树，所有的节点data域为0。再一个节点一个节点地添加。把每个数按照自己的离散值，放到树中合适的位置，然后data域+1，回溯的时候也要+1。当然，不能放到那棵空树中，要重新建树。第i棵树存的是区间（原序列）[1,i]。但是，如果是这样，那么会MLE+TLE。因此，要充分利用历史版本。用两个指针，分指当前空树和前一棵树。因为每棵树的结构是一样的，只是里面的data域不同，但是两棵相邻的树，只有一数只差，因此，如果元素要进左子树的话，右子树就会跟上个树这个区间的右子树是完全一样的，因此，可以直接将本树本节点的右子树指针接到上棵树当前节点的右儿子，这样即省时间，又省空间。
每添加一个节点（也就是新建一棵树）的复杂度是O(logn)，因此，这一步的复杂度是O(nlogn)。
建完之后，要怎么查找呢？
跟一般的，在整棵树中找第k个数是一样的。如果一个节点的左权值（左子树上点的数量之和）大于k，那么就到左子树查找，否则到右子树查找。其实主席树是一样的。对于任意两棵树（分别存区间[1,i]和区间[1,j] i<j），在同一节点上（两节点所表示的区间相同），data域之差表示的是，原序列区间[i,j]在当前节点所表示的区间里，出现多少次（有多少数的大小是在这个区间里的）。同理，对于同一节点，如果在两棵树中，它们的左权值之差大于等于k，那么要求的数就在左孩子，否则在右孩子。当定位到叶子节点时，就可以输出了。
题目：
VIJOS P1081
POJ 2104
代码：
program p1081;{Chairtree}
type
wv1=^wv2;
wv2=record
lc, //左右孩子；
rc:wv1;
lft,rht, //区间左右端点；
data:longint; //出现次数（存了的元素个数）；
end;
var
tree:array[0..100000] of wv1;
a,b,c:array[1..100000] of longint;//a：原数组+排序后的数组；b：原数组中每个数的原序号；c：离散后的值；
n,m,i,k,xx,ll,rr:longint;
procedure quick(q1,q2:longint);//对原数组排序
var
i,j,x:longint;
begin
i:=q1;j:=q2;x:=a[q1];
while i<j do
begin
while (i<j) and (x<=a[j]) do j:=j-1;
if i<j then
begin
a[i]:=a[j];
k:=b[i];
b[i]:=b[j];
b[j]:=k;
end;
while (i<j) and (a[i]<=x) do i:=i+1;
if i<j then
begin
a[j]:=a[i];
k:=b[i];
b[i]:=b[j];
b[j]:=k;
end;
a[i]:=x;
end;
if i>q1+1 then quick(q1,i-1);
if j<q2-1 then quick(j+1,q2);
end;
procedure index1; //离散化；
begin
for i:=2 to n do
if a[i]=a[i-1] then begin
c[b[i]]:=c[b[i-1]];
end
else c[b[i]]:=i;
end;
procedure build(j:wv1;l,r:longint); //建第一棵树；
var
mid:longint;
begin
j^.lft:=l;j^.rht:=r;
j^.data:=0; //data域为0；
mid:=(l+r)>>1;
new(j^.lc);
if j^.lft=j^.rht then j^.lc:=nil
else build(j^.lc,l,mid);
new(j^.rc);
if j^.lft=j^.rht then j^.rc:=nil
else build(j^.rc,mid+1,r);
end;
procedure scarlet(j,ju:wv1;l,r:longint); //j指新建的树，ju值上一棵树；
var
mid:longint;
begin
j^.data:=ju^.data;
mid:=(l+r)>>1;
new(j^.lc);new(j^.rc);
j^.lft:=l;j^.rht:=r;
if l=r then
begin
j^.lc:=nil;
j^.rc:=nil;
j^.data:=j^.data+1;
exit;
end else
begin
if c[i]<=mid then
begin
j^.rc:=ju^.rc;
scarlet(j^.lc,ju^.lc,l,mid);
j^.data:=j^.data+1;
end else
if c[i]>mid then
begin
j^.lc:=ju^.lc;
scarlet(j^.rc,ju^.rc,mid+1,r);
j^.data:=j^.data+1;
end;
end;
end;
procedure index2; //依次创建每棵树；
begin
for i:=1 to n do
begin
new(tree[i]);
tree[i]^.lft:=1;tree[i]^.rht:=n;tree[i]^.data:=0;
scarlet(tree[i],tree[i-1],1,n)
end;
end;
function find(j,ju:wv1;k:longint):longint; //j指新建的树，ju值上一棵树；
var
oy:longint;//data域之差；
j1,j2:wv1;
begin
if j^.lft=j^.rht then exit(j^.rht);
j1:=j^.lc;j2:=ju^.lc;
oy:=j1^.data-j2^.data;
if oy>=k then
find:=find(j^.lc,ju^.lc,k)
else
begin
find:=find(j^.rc,ju^.rc,k-(oy));
end;
end;
{===================================}
begin
assign(input,'p1081.in');
assign(output,'p1081.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do begin read(a[i]);b[i]:=i;end;
readln;
quick(1,n);
c[b[1]]:=1;
index1;
new(tree[0]);
build(tree[0],1,n);
index2;
for xx:=1 to m do
begin
readln(ll,rr,k);
writeln(a[find(tree[rr],tree[ll-1],k)]); //函数返回的是离散值，也就是在排完序的数组的下标；
end;
end.
网上的教程很少啊，有的教程写得特别简单，4行中文，然后就是一篇代码～～
这里，我将从查找区间第k小值（不带修改）题的可持久化线段树做法中，讲一讲主席树。
/*只是略懂，若有错误，还请多多包涵！*/
可持久化数据结构(Persistent data structure)就是利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。/*找不到比较科学的定义，就拿这个凑凑数吧～～～*/
这个数据结构很坑啊，我研究了一整天才差不多理解了一些（。。太笨了。。。）。所以，要理解好每一个域或变量的意义。
开讲！
一些数据结构，比如线段树或平衡树，他们一般是要么维护每个元素在原序列中的排列顺序，要么是维护每个元素的大小顺序，若是像二者兼得。。（反正我是觉得很。。）那么，这道题就想想主席树吧～/*还可以用划分树做*/
开讲！～好像说过一边了
既然叫“函数式线段树”，那么就应该有跟普通线段树相同的地方。一颗线段树，只能维护一段区间里的元素。但是，每个询问的区间都不一样，若是对每段区间都单独建立的线段树，那～萎定了～。因此，就要想，如何在少建，或建得快的情况下，能利用一些方法，得出某个区间里的情况。
比如一棵线段树，记为tree[i][j]，表示区间[i,j]的线段树。那么，要得到它的情况，可以利用另外两棵树，tree[1][i-1]和tree[1][j]，得出来。也就是说，可以由建树的一系列历史版本推出。
那么，怎么创建这些树呢？
首先，离散化数据。因为如果数据太大的话，线段树会爆～～
在所有树中，是按照当前区间元素的离散值（也就是用大小排序）储存的，在每个节点，存的是这个区间每个元素出现的次数之和（data域）。出现的次数，也就是存了多少数进来（建树时，是一个数一个数地存进来的）。
先建议棵线段树，所有的节点data域为0。再一个节点一个节点地添加。把每个数按照自己的离散值，放到树中合适的位置，然后data域+1，回溯的时候也要+1。当然，不能放到那棵空树中，要重新建树。第i棵树存的是区间（原序列）[1,i]。但是，如果是这样，那么会MLE+TLE。因此，要充分利用历史版本。用两个指针，分指当前空树和前一棵树。因为每棵树的结构是一样的，只是里面的data域不同，但是两棵相邻的树，只有一数只差，因此，如果元素要进左子树的话，右子树就会跟上个树这个区间的右子树是完全一样的，因此，可以直接将本树本节点的右子树指针接到上棵树当前节点的右儿子，这样即省时间，又省空间。
每添加一个节点（也就是新建一棵树）的复杂度是O(logn)，因此，这一步的复杂度是O(nlogn)。
建完之后，要怎么查找呢？
跟一般的，在整棵树中找第k个数是一样的。如果一个节点的左权值（左子树上点的数量之和）大于k，那么就到左子树查找，否则到右子树查找。其实主席树是一样的。对于任意两棵树（分别存区间[1,i]和区间[1,j] i<j），在同一节点上（两节点所表示的区间相同），data域之差表示的是，原序列区间[i,j]在当前节点所表示的区间里，出现多少次（有多少数的大小是在这个区间里的）。同理，对于同一节点，如果在两棵树中，它们的左权值之差大于等于k，那么要求的数就在左孩子，否则在右孩子。当定位到叶子节点时，就可以输出了。
题目：
VIJOS P1081
POJ 2104
代码：
program p1081;{Chairtree}
type
wv1=^wv2;
wv2=record
lc, //左右孩子；
rc:wv1;
lft,rht, //区间左右端点；
data:longint; //出现次数（存了的元素个数）；
end;
var
tree:array[0..100000] of wv1;
a,b,c:array[1..100000] of longint;//a：原数组+排序后的数组；b：原数组中每个数的原序号；c：离散后的值；
n,m,i,k,xx,ll,rr:longint;
procedure quick(q1,q2:longint);//对原数组排序
var
i,j,x:longint;
begin
i:=q1;j:=q2;x:=a[q1];
while i<j do
begin
while (i<j) and (x<=a[j]) do j:=j-1;
if i<j then
begin
a[i]:=a[j];
k:=b[i];
b[i]:=b[j];
b[j]:=k;
end;
while (i<j) and (a[i]<=x) do i:=i+1;
if i<j then
begin
a[j]:=a[i];
k:=b[i];
b[i]:=b[j];
b[j]:=k;
end;
a[i]:=x;
end;
if i>q1+1 then quick(q1,i-1);
if j<q2-1 then quick(j+1,q2);
end;
procedure index1; //离散化；
begin
for i:=2 to n do
if a[i]=a[i-1] then begin
c[b[i]]:=c[b[i-1]];
end
else c[b[i]]:=i;
end;
procedure build(j:wv1;l,r:longint); //建第一棵树；
var
mid:longint;
begin
j^.lft:=l;j^.rht:=r;
j^.data:=0; //data域为0；
mid:=(l+r)>>1;
new(j^.lc);
if j^.lft=j^.rht then j^.lc:=nil
else build(j^.lc,l,mid);
new(j^.rc);
if j^.lft=j^.rht then j^.rc:=nil
else build(j^.rc,mid+1,r);
end;
procedure scarlet(j,ju:wv1;l,r:longint); //j指新建的树，ju值上一棵树；
var
mid:longint;
begin
j^.data:=ju^.data;
mid:=(l+r)>>1;
new(j^.lc);new(j^.rc);
j^.lft:=l;j^.rht:=r;
if l=r then
begin
j^.lc:=nil;
j^.rc:=nil;
j^.data:=j^.data+1;
exit;
end else
begin
if c[i]<=mid then
begin
j^.rc:=ju^.rc;
scarlet(j^.lc,ju^.lc,l,mid);
j^.data:=j^.data+1;
end else
if c[i]>mid then
begin
j^.lc:=ju^.lc;
scarlet(j^.rc,ju^.rc,mid+1,r);
j^.data:=j^.data+1;
end;
end;
end;
procedure index2; //依次创建每棵树；
begin
for i:=1 to n do
begin
new(tree[i]);
tree[i]^.lft:=1;tree[i]^.rht:=n;tree[i]^.data:=0;
scarlet(tree[i],tree[i-1],1,n)
end;
end;
function find(j,ju:wv1;k:longint):longint; //j指新建的树，ju值上一棵树；
var
oy:longint;//data域之差；
j1,j2:wv1;
begin
if j^.lft=j^.rht then exit(j^.rht);
j1:=j^.lc;j2:=ju^.lc;
oy:=j1^.data-j2^.data;
if oy>=k then
find:=find(j^.lc,ju^.lc,k)
else
begin
find:=find(j^.rc,ju^.rc,k-(oy));
end;
end;
{===================================}
begin
assign(input,'p1081.in');
assign(output,'p1081.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do begin read(a[i]);b[i]:=i;end;
readln;
quick(1,n);
c[b[1]]:=1;
index1;
new(tree[0]);
build(tree[0],1,n);
index2;
for xx:=1 to m do
begin
readln(ll,rr,k);
writeln(a[find(tree[rr],tree[ll-1],k)]); //函数返回的是离散值，也就是在排完序的数组的下标；
end;
end.
RSS Feed