本文涉及的源代码及文章请点击这里下载。
这篇文章讨论的是序列中第K大或第K小元素，由于第K大元素可以转化为求第N-K+1小元素（N为序列的长度），所以，本文专注于讨论第K小元素。 本文讨论的几个问题：
对给定整数序列，求该序列中第K小的元素。 对某一整数序列，允许动态更改序列中的数。动态查询序列中第K小元素。 给定一个整数序列和若干个区间，回答该区间内第K小元素。 对某一整数序列，允许动态更改序列中的数。动态查询序列中的第K小元素。 关键字 第K小元素 树状数组 线段树 平衡二叉树 归并树 划分树 单调队列 堆 块状表
问题一 问题描述： 给出一个乱序整数序列a[1…n] ，求该序列中的第K小元素。（1<=K<=N）。
算法分析： 用基于快速排序的分治算法，期望复杂度为O(N)。
代码： int qs(int *a , int l , int r , int k){ if(l == r) return a[l] ; int i = l , j = r , x = a[(l+r)>>1] , temp ; do{ while(a[i] < x) ++ i ; while(a[j] > x) -- j ; if(i <= j){ temp = a[i] ; a[i] = a[j] , a[j] = temp ; i++ ; j-- ; } }while(i<=j) ; if(k <= j) return qs(a , l , j , k); if(k >= i) return qs(a , i , r , k); return x ; } 练习 RQNOJ 350 这题数据量比较小1≤N≤10000,1≤M≤2000 。所以计算量不会超过10^7。当然用到后面的归并树或划分树，能将复杂度降低。
【问题二】 问题描述： 给出一个乱序整数序列a[1…n] ，有3种操作：
操作一：ADD NUM 往序列添加一个数NUM。 操作二：DEL NUM 从序列中删除一个数NUM（若有多个，只删除一个）。
操作三：QUERY K 询问当前序列中第K小的数。
输出每次询问的数。假设操作的次数为M。
算法分析： 这题实际上就是一边动态增删点，一边查询第K小数。这类题有两种思维方法：一是二分答案，对当前测试值mid，查询mid在当前序列中的排名rank ， 然后根据rank决定向左边还是右边继续二分。另一种是直接求第K小元素。
这个题可以用各种类型的数据结构解决，其时间复杂度和编程复杂度稍有区别：
线段树：运用第一种思维，当添加（删除）一个数x时，相当于往线段树上添加（删除）一条(x , maxlen)（注意是闭区间）长度的线段。这样询问时，覆盖[mid , mid]区间的线段数就是比mid小的数，加上1就是rank。二分次数为log(maxlen) ，查一次mid的rank ， 复杂度为O(logN) 。所以总复杂度上界为O(MlogNlogN) 。为方便比较，这里认为log(maxlen)等于logN。
...