【模板】划分树

Kth Number

多次询问一个静态区间里的第k大数。怎么搞？

暴力？（还是别想了）

多次构建树状数组？（和暴力有啥区别）

于是一个叫做划分树的东西就登场了。（据说还有个叫归并树的，速度慢一点，就不学了）

划分树详解

——代码

1 #include <cstdio> 2 #include <algorithm> 3 #define N 100001 4 5 using namespace std; 6 7 int n, m; 8 int c[N];//排序后数组 9 int num[20][N], val[20][N]; 10 //一共有20层，每一层元素排放，0层是原数组 11 //num[i] 表示 i 前面有多少个孩子进入左孩子 12 13 inline void build(int l, int r, int k) 14 30 else val[k + 1][rc++] = val[k][i];//到右孩子 31 } 32 build(l, mid, k + 1); 33 build(mid + 1, r, k + 1); 34 } 35 36 inline int query(int l, int r, int k, int ql, int qr, int qk) 37 50 } 51 52 int main() 53 65 } 66 return 0; 67 }
View Code

当然还有其他方法，不过代码量都比较大。

可以看看这篇blog

上一篇：[HDU3065]病毒持续侵袭中（AC自动机）

下一篇：【模板】Treap

---

模板 划分树