主席树学习笔记 Lv. 1

接上文。。。)

函数式(现在又称主席式。。。)数据结构从来都没写过,感觉这个东西可以挖掘出不少东西出来,于是开一组专题。
先根据 Seter 留下的文本做一些记录。。

主席树大概是一种离线结构,我以前反正没看到过这东西,所以就自己给他起名字了!如果谁知道这东西的真名,请告诉我!

现在我们知道,主席树的全名应该是 函数式版本的线段树。加上附带的一堆 technology。。
。。总之由于原名字太长了,而且 “主席” 两个字念起来冷艳高贵,以后全部称之为主席树好了。。。

主席树的主体是线段树,准确的说,是很多棵线段树,存的是一段数字区间出现次数(所以要先离散化可能出现的数字)。举个例子,假设我每次都要求整个序列内的第 k 小,那么对整个序列构造一个线段树,然后在线段树上不断找第 k 小在当前数字区间的左半部分还是右半部分。这个操作和平衡树的 Rank 操作一样,只是这里将离散的数字搞成了连续的数字。

先假设没有修改操作:

对于每个前缀 S1…i,保存这样一个线段树 Ti,组成主席树。这样不是会 MLE 么?最后再讲。

注意,这个线段树对一条线段,保存的是这个数字区间的出现次数,所以是可以互相加减的!还有,由于每棵线段树都要保存同样的数字,所以它们的大小、形态也都是一样的!这实在是两个非常好的性质,是平衡树所不具备的。

对于询问 (i,j),我只要拿出 Tj 和 Ti-1,对每个节点相减就可以了。说的通俗一点,询问 i..j 区间中,一个数字区间的出现次数时,就是这些数字在 Tj 中出现的次数减去在 Ti-1 中出现的次数。

那么有修改操作怎么办呢?

如果将询问看成求一段序列的数字和,那么上面那个相当于求出了前缀和。加入修改操作后,就要用树状数组等来维护前缀和了。于是那个 “很好的性质” 又一次发挥了作用,由于主席树可以互相加减,所以可以用树状数组来套上它。做法和维护前缀和长得基本一样,不说了。

这段指出了主席树的主要性质。。

  • 线段树的每个结点,保存的是这个区间含有的数字的个数。
  • 主席树的每个结点,也就是每颗线段树的大小和形态也是一样的,也就是主席树之间可以相互进行加减运算。。

同时我们也枚举一下主席树的一些局限:

  • 主席树是一种离线结构。。(必须预先知道所有数字的范围。。这在一些应用中会成为障碍。。。
  • 存在 MLE 问题。。(如果按照定义里面的方法去写,对每个结点都需要开一整可线段树,至少都是 O(n2) 级别的空间。。

——————————————————
开始填坑。由于每棵线段树的大小形态都是一样的,而且初始值全都是 0,那每个线段树都初始化不是太浪费了?所以一开始只要建一棵空树即可。

然后是在某棵树上修改一个数字,由于和其他树相关联,所以不能在原来的树上改,必须弄个新的出来。难道要弄一棵新树?不是的,由于一个数字的更改只影响了一条从这个叶子节点到根的路径,所以只要只有这条路径是新的,另外都没有改变。比如对于某个节点,要往右边走,那么左边那些就不用新建,只要用个指针链到原树的此节点左边就可以了,这个步骤的前提也是线段树的形态一样。

假设s是数字个数,这个步骤的空间复杂度显然是 O(logs)。用树状数组去套它,共有 2logn 棵树被修改,m 个操作再加上一开始的空树和 n 个数字,总共就是 O((n+m)lognlogs)。Fotile 大神说如果加上垃圾回收的话,可以去掉一个 log…… ym

至此主席树结构已经分析清楚了。。

const int N = 50009, M = 10009, NN = 2500009;

int l[NN], r[NN], c[NN], total;

PII A[N+M]; int B[N+M], Q[M][3];
int S[N], C[N], Null;
int n, m, An, Tn;
.. .

这里仍然用池子法保存线段树的结点,NN 是一个估计值。。(大概是 nlogn 。。。
l[], r[], c[], total 分别是左孩子下标,右孩子下标,该区间的数字个数和当前已分配的结点数。
(线段树的区间可以在递归的时候实时计算,可以不予保存。。。

PII A[]; int B[]; A、B 用于离散化。。。 B 记录相应数字的 Rank 值。
int Q[]; 记录询问。。。

int S[], C[], Null; 是主席树下标。。
分别对应前缀和,树状数组 和 初始时的空树。

An 是 A 数组的长度,由初始 n 个数字和修改后的数字决定,
Tn 是所有出现的不同数字的个数,用于建立线段树,由对 A 数组去重后得到。

#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define cx c[x]
#define cy c[y]

#define mid ((ll+rr)>>1)
#define lc lx, ll, mid
#define rc rx, mid+1, rr


void Build(int &x, int ll, int rr){
    x = ++total; if (ll < rr) Build(lc), Build(rc);
}

int Insert(int y, int p, int d){

    int x = ++total, root = x;

    c[x] = c[y] + d; int ll = 0, rr = Tn;

    while (ll < rr){
        if (p <= mid){
            lx = ++total, rx = ry;
            x = lx, y = ly, rr = mid;
        }
        else {
            lx = ly, rx = ++total;
            x = rx, y = ry, ll = mid + 1;
        }
        c[x] = c[y] + d;
    }

    return root;
}

这里是主席树主要支持的操作。。前面一堆 Macro 方便敲代码。。。
注意由于 l[], r[], 还有 m 全部有冲突干脆用 ll, rr, mid 代替区间下标。。。

这里 Insert() 过程就是前面所说的插入单链的操作。。。以 y 为基础,形成一棵新的主席树 x。
。。。没有修改的链仍然指向 y 的相对应部分。复杂度为树高。。。。

。。。下面是 int main(); 函数代码了。。。完整程序移步这里。。。。

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

#define key first
#define id second

    RD(n, m); REP(i, n) A[i] = MP(RD(), i);

    An = n; char cmd; REP(i, m){
        RC(cmd); if(cmd == 'Q') RD(Q[i][0], Q[i][1], Q[i][2]);
        else RD(Q[i][0]), Q[i][2] = 0, A[An++] = MP(RD(), An);
    }

    sort(A, A + An), B[A[0].id] = Tn = 0;
    FOR(i, 1, An){
        if(A[i].key != A[i-1].key) A[++Tn].key = A[i].key;
        B[A[i].id] = Tn;
    }

    Build(Null, 0, Tn); REP_1(i, n) C[i] = Null;

    S[0] = Null; REP(i, n){
        S[i+1] = Insert(S[i], B[i], 1);
    }

    An = n;

    REP(i, m) if (Q[i][2]){
        OT(A[Query(Q[i][0], Q[i][1], Q[i][2])].key);
    }else{
        Modify(Q[i][0], B[Q[i][0]-1], -1);
        Modify(Q[i][0], B[Q[i][0]-1] = B[An++], 1);
    }
}

待讨论问题:


  1. 由于每棵线段树的大小形态都是一样的,而且初始值全都是 0,那每个线段树都初始化不是太浪费了?所以一开始只要建一棵空树即可。

    事实上由于当一个结点的 c[] 结果为 0 时。。无论它向左还是向右递归下去结果都会是0 。。。
    所以初始时甚至不是建立空树。。而是只需要一个空结点即可。。。(如何实现这层。。。

  2. 仍然没有将 Lazy Evalutaion 的理念做到完美。。。这题中的 Lazy Evaluation 体现在两个方面。。
    主席树的单链修改和主席树与主席树之间的运算。。

    主席树与主席树之间的运算如果全部做的话一次是 O(n)。。。但是因为询问时只需要计算一条到叶子的路径。。。
    。。。上面的代码中,这种运算是通过 Struct Pack; 结构体现的。。。一种多颗主席树结点的打包。。
    。。全部在同一层的同一个位置。。向同一个方向递归下降。。一个 Pack; 的值为该结构内所有结点值的和。。

    。。现在实现的不足之处:

    • 无法很好的处理减运算。。因此这里才还要保存了 S[] 前缀和,让 C[] 逐个逐个修改。。。
      。。。然后每次回答询问的时候还要一并带上 S[] 。。Orz。(虽然说有助于预处理。。
    • 对计算过后结果无法有效利用。。(换句话说没有体现出主席式 Memorization 的一面。。。
    • 对单个链的插入操作也不是要即时处理的。。(。。如何用数据结构把所有操作先 Hold 下来 。。?。。这样的好处是有一些操作对结果没有影响是可以忽略。。另外把一堆操作放在一起当做一个操作处理的话有时也能得到 Bonus 。。。
  3. Fotile 大神说如果加上垃圾回收的话,可以去掉一个 log…… ym

    (另外正一个误。。。加上回收并不能去掉一个 log 。。。。