一：静态主席树
推荐的博客： http://www.cnblogs.com/zyf0163/p/4749042.html
静态的主席树和划分树类似，只不过是用的线段树存放。
#include#include #include #include #include using namespace std;const int N = 100000 + 5;int a[N], b[N], rt[N * 20], ls[N * 20], rs[N * 20], sum[N * 20];//rt[i]表示处理完前i个数之后所形成的线段树//sum[i]表示当前l-r范围内有几个点被更新了//ls[i]表示编号为rt[i]这个点的左儿子为rt[ls[i]]//那么rt[r] - rt[l-1]即表示处理的[l, r]区间,对应点的sum相减//到区间[l, r]的数要查询第k大便很容易了，设左节点中存的个数为cnt，当k<=cnt时，我们直接查询左儿子中第k小的数即可，如果k>cnt，我们只要去查右儿子中第k-cnt小的数即可int n, k, tot, sz, ql, qr, x, q, T;void Build(int& o, int l, int r){ o = ++ tot; sum[o] = 0; if(l == r) return; int m = (l + r) >> 1; Build(ls[o], l, m); Build(rs[o], m + 1, r);}void update(int& o, int l, int r, int last, int p){ o = ++ tot; ls[o] = ls[last]; rs[o] = rs[last]; sum[o] = sum[last] + 1; if(l == r) return; int m = (l + r) >> 1; if(p <= m) update(ls[o], l, m, ls[last], p); else update(rs[o], m + 1, r, rs[last], p);}int query(int ss, int tt, int l, int r, int k){ if(l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]]; if(k <= cnt) return query(ls[ss], ls[tt], l, m, k); else return query(rs[ss], rs[tt], m + 1, r, k - cnt);}void work(){ scanf("%d%d%d", &ql, &qr, &x); int ans = query(rt[ql - 1], rt[qr], 1, sz, x); printf("%d\n", b[ans]);}int main(){ scanf("%d", &T); while(T--){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = a[i]; sort(b + 1, b + n + 1); sz = unique(b + 1, b + n + 1) - (b + 1); tot = 0; Build(rt[0],1, sz); //for(int i = 0; i <= 4 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); for(int i = 1; i <= n; i ++)a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b; for(int i = 1; i <= n; i ++)update(rt[i], 1, sz, rt[i - 1], a[i]); //for(int i = 0; i <= 5 * n; i ++)printf("%d,rt = %d,ls = %d, rs = %d, sum = %d\n", i, rt[i], ls[i], rs[i], sum[i]); while(q --)work(); } return 0;}
但静态主席树仍无法修改初始区间的信息。
二：动态主席树
使用了树状数组来存放前缀线段树，即树状数组中的每一个点都是线段树。但这棵线段树不再保存每个前缀的信息了，而是由树状数组的sum函数计算出这个前缀的信息，那么显而易见这棵线段树保存的是辅助数组S的值，即S=A[i-lowbit+1]+...+A[i],其中A[i]表示值为i的元素出现的次数。然后初始时建立一颗静态的主席树，树状数组只保存每次修改的信息。
表示不明白，大概能用。
#include#include #include #include #include #include #include #include #include #include #include