The K-th Element in Algorithms

Source code and related articles are available here.

This article discusses the K-th largest or K-th smallest element in a sequence. Since the K-th largest can be reduced to finding the (N−K+1)-th smallest (where N is the sequence length), we focus on the K-th smallest element.

Problems covered in this article:

1. Given an integer sequence, find the K-th smallest element.
2. Given an integer sequence that supports dynamic updates, answer queries for the K-th smallest element.
3. Given an integer sequence and several intervals, answer the K-th smallest element in each interval.
4. Given an integer sequence that supports dynamic updates, answer queries for the K-th smallest element in an interval.

Keywords

K-th smallest element Fenwick tree (Binary Indexed Tree) Segment tree Balanced binary search tree Merge tree Partition tree Monotonic queue Heap Sqrt decomposition (block decomposition)

Problem 1

• Problem description:

Given an unsorted integer sequence a[1…n], find the K-th smallest element. (1<=K<=N).

• Algorithm analysis:

Use a divide-and-conquer algorithm based on quicksort. Expected time complexity is O(N).

• Code:

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 ;
}

• Practice

RQNOJ 350 The data size is relatively small: 1≤N≤10000, 1≤M≤2000, so the total work stays below 10^7. Of course, using a merge tree or partition tree later can reduce the complexity further.

Problem 2

• Problem description:

Given an unsorted integer sequence a[1…n], there are three operations:

Operation 1: ADD NUM — add NUM to the sequence.
Operation 2: DEL NUM — remove one occurrence of NUM from the sequence (if there are multiple, remove only one).
Operation 3: QUERY K — ask for the K-th smallest number in the current sequence.

Output the answer to each query. Assume there are M operations.

• Algorithm analysis:

This is essentially dynamic insert/delete with queries for the K-th smallest. There are two ways to think about such problems: (1) binary search on the answer — for a candidate mid, compute its rank in the current sequence and decide whether to search left or right; (2) directly find the K-th smallest element.

This problem can be solved with various data structures, with slightly different time and implementation complexity:

• Segment tree: Using the first approach, when adding (or deleting) a value x, it is equivalent to adding (or removing) a segment of length (x, maxlen) on the segment tree (note: closed interval). Then when querying, the number of segments covering [mid, mid] is the count of values smaller than mid; adding 1 gives the rank. The number of binary-search steps is log(maxlen), and each rank query costs O(log N), so the overall upper bound is O(MlogNlogN). For comparison, we assume log(maxlen) equals logN.

• Fenwick tree (Binary Indexed Tree):

First approach: This is relatively simple — counting values smaller than mid is just getsum(mid-1).

Same complexity as the segment tree, but with a much smaller constant factor and far less code.

Second approach: I can only say it is very clever. Recall the Fenwick tree prefix-sum operation:

• Code

int getsum(int x ){
    int res = 0 ;
    for( ; x>0 ; x-=lowbit(x) )  res += arr[x] ;
    return res ;  
}

For the binary number 10100010, we successively accumulate arr[10100010], arr[10100000], arr[10000000] to obtain the count of values less than x. Reversing this idea gives the following method: from high bit to low bit, determine whether each bit of the answer is 0 or 1. First assume it is 1; if the accumulated count would exceed K, the assumption fails and the bit should be 0; otherwise continue to the next bit. The code makes it clear.

• Code

int getkth(int k){
        int ans = 0 , cnt = 0 , i ;
        for(i = 20 ; i>=0 ; --i){
                ans += 1<<i ;
                if(ans>=maxn||cnt+c[ans]>=k) ans-=1<<i ;
                else cnt +=c[ans] ;      
        }
        return ans+1 ; 
    }

Complexity: Naturally one log factor less than the first approach. O(M*logN).

• Balanced binary search tree:

Any balanced BST can solve this: Size Balanced Tree, Splay, Treap, red-black tree, and so on. It must be said that the Size Balanced Tree is quite convenient here, because the SBT already has a Select operation — call it and you are done.

• Code

Complexity: Uses the second approach. O(M*logN).

• Summary:

Overall, there are many data structures, many algorithms, and much to weigh. Balanced trees are too complex; segment trees are a bit heavy (though usually fine in practice). The best approach is still the binary Fenwick tree method — a win on both time and implementation complexity.

But in summary, segment trees and Fenwick trees consume space proportional to the value range. When elements are floating-point or the range is very large, they struggle (offline cases can be discretized; some online cases can too), while balanced BSTs do not have this problem. So balanced BSTs are the real king.

• Practice:

I have recently found that problems based on this idea are quite numerous~ ~

POJ Double Queue

NOI2004 Depressed Cashier View wages in reverse: employee salaries stay fixed, but the minimum wage floor changes. When lowering the wage floor, to know which employees leave, I also used a binary heap…

POJ 2761 Feed the dogs This problem is first a special case of Problem 3 below. Its special property is that any two intervals are disjoint, so after sorting intervals by left endpoint (no duplicate left endpoints, otherwise one would contain the other), scan each interval in order: keep the overlap between the current interval and the previous one unchanged, delete the part in the previous interval but not in the current one, and add the part in the current interval but not in the previous one. This ensures each element is added and deleted exactly once.

POJ 2823 Sliding Window Very special: the maximum is the K-th smallest, and the minimum is the 1st smallest (an important insight: Fenwick trees can also maintain dynamic extrema). A monotonic queue can achieve linear time.

HUNNU 10571 Counting Girls The 4th Central South Invitational, but the data differs slightly from the statement. It can be confirmed that each number is ≥ 0 and ≤ 200000. The key is summing ratings from the X-th to the Y-th “MM” — pay attention to that.

KiKi’s K-Number Nothing much to say about this one. To find the K-th smallest in [a+1, MaxInt], first count how many numbers are in [0, a], call it cnt, then find the (K+cnt)-th smallest. Oh, the problem says K-th largest, but it actually asks for K-th smallest — interesting~

Problem 3

• Problem description

Given a sequence a[1…n] and m queries, each query asks for the K-th smallest number in a[i…j]. (Quoting the English constraint: You can assume that n<100001 and m<50001)

• Algorithm analysis

• Sqrt decomposition (block decomposition)

If you can think of sqrt decomposition for this problem, both the conceptual and coding complexity are modest~ Consider the following:

First preprocess by splitting the sequence into sqrt(N) blocks, each of length [sqrt(N)]. When partitioning, sort each block.

For a query on [i, j], again binary-search the count of values smaller than a test value mid. Enumerate the two partial blocks at the ends of i and j directly; for complete blocks in the middle, binary search within each block. The time complexity of one query is

So the total complexity is:

Of course, the constant factor is large; a program I wrote still timed out. But when M is small, it is still a reasonable choice (or at least good for broadening your thinking — and it barely works for Problem 4).

• Partition tree

The partition tree should be the lowest-complexity method for this problem:

The idea is actually simple: use a segment tree to partition the whole sequence into intervals. When building, for interval [l, r]: choose the median value of that interval (note: you can quicksort the original sequence first to get medians quickly), put at most mid−l+1 values ≤ value into [l, mid], and the rest into [mid+1, r]. Save the sequence at each level in an array.

When searching, Find(x, l, r, k) means finding the K-th smallest in interval [l, r] within node x. Split the node interval into three parts [seg_left, l-1], [l, r], [r+1, seg_right]; during partitioning, the counts assigned to [l, mid] are ls, ms, rs respectively. If ms <= K, search the left child naturally: Find(2*x, l+ls, l+ls+ms-1, K). Otherwise search the right; index arithmetic is annoying. Code below~

• Code

void build(lld d ,lld l , lld r ){
    if(l == r)  return  ;
    lld i , mid = (l+r)>>1 , j=l , k=mid+1  ;
    for(i = l ; i <= r ; ++ i){
        s[d][i] = s[d][i-1] ; 
        if(tr[d][i] <= mid){
            s[d][i]++ ;  
            tr[d+1][j++] = tr[d][i]; 
        }else{
            tr[d+1][k++] = tr[d][i];
        }
    }
    build(d+1 ,l , mid);
    build(d+1 , mid+1 , r);
}

lld getkth(lld d ,lld lp ,lld rp , lld l , lld r , lld k){
    if(lp == rp )  return tr[d][lp] ;
    lld mid = (lp + rp)>>1 ; 
    if(k<=s[d][r]-s[d][l-1])
        return getkth(d+1 ,lp , mid , 
            lp+s[d][l-1]-s[d][lp-1] ,
            lp+s[d][r]-s[d][lp-1]-1 ,
            k);
    else 
        return getkth(d+1 ,mid+1 , rp ,
            mid+1+(l-lp)-(s[d][l-1]-s[d][lp-1]) , 
            mid+(r-lp+1)-(s[d][r]-s[d][lp-1]) ,
            k-(s[d][r]-s[d][l-1]) );
}

• Merge tree

The merge tree idea is even simpler: in essence, sort and store all numbers in each segment-tree interval [l, r]. From two children to a parent, it is just merging two sorted sequences — hence the name merge tree. Using binary search on the answer as described earlier, for test value mid compute rank. When querying, decompose the query interval into a union of several segment-tree nodes; clearly the sum of counts < mid over those sub-intervals is the total count < mid in the query range. Each sub-interval is sorted, so binary search quickly finds the count < mid in each. In summary, there are three levels of binary search:

1. Binary search on the answer;
2. Decompose query interval [a, b] into at most log(b − a) sub-intervals;
3. For each sub-interval, binary search for the count < mid;

Thus the overall complexity is:

• Summary:

For this problem, three algorithms are provided. The quicksort-based partition approach is the fastest; sqrt decomposition is simple in concept and code but has higher complexity; the merge tree has a beautiful idea — binary search on the answer, compute rank — and the algorithm for Problem 4 is designed along these lines.

• Practice

POJ 2761 Feed the dogs

POJ 2104 K-th Number

NOI 2010 Super Piano This one is genuinely difficult.

Approach: partition tree + heap + monotonic queue

For each interval, the start is i+1 and the end lies in [i+L, i+R]. Let s[i] = a[0]+a[1]+...+a[i] (with a[0]=0). Let opt[i,k] denote the k-th largest s[j] with i+L<=j<=i+R, i.e. opt[i,k] = Max_k { s[j] | i+L<=j<=i+R} (Max_k means k-th largest).

Two preprocessing steps:

1. Build a static partition tree on s[1], s[2], s[3], .. s[n].

2. Use a monotonic queue to preprocess all opt[i,1] values, and maintain all opt[i,1]−s[i] in a heap. Alternatively, preprocess opt[i,1] directly by querying the 1st largest value in [i+L, i+R].

Then extract and update: repeatedly take the maximum from the heap, say opt[i,j]−s[i], add it to the answer, query the (j+1)-th largest value opt[i,j+1] in [i+L, i+R] on the partition tree, and push opt[i,j+1]−s[i] into the heap. Stop after K accumulations.

Problem 4

• Problem description

Given an initial sequence a[1…n], there are two operations:

Operation 1: QUERY i j k — ask for the k-th smallest number in a[i…j] in the current sequence
Operation 2: CHANGE i T — set a[i] to T;
Output the result of each query. N<=50000 , number of operations M<=10000

• Algorithm analysis

• Sqrt decomposition

Split a[1…n] into sqrt(N) blocks, each of length [sqrt(N)]. To support binary search within each block, keep each block sorted. For operation 2, remove a[i], insert T, and maintain the block’s sorted order — O(sqrt(N)).

For operation 1, binary search on the answer with test value mid: first scan the two partial end blocks, O(2*sqrt(N)). For complete middle blocks, binary search in each block. Total complexity:

• Segment tree + balanced BST

The sequence is partitioned by a segment tree into interval nodes, and each node holds a balanced BST containing all values in that segment.

For operation 2, update the balanced trees from the root interval down to the leaf (delete a[i], insert T). Layer 1 has size N, layer 2 has N/2, layer k has N/2^k. The cost of one operation 2 is:

Here K = [logN]

For operation 1: the query interval is decomposed into at most [logN] segment-tree nodes, and each interval lookup is bounded by logN. So for each test value mid, the cost is (logN)^2; one query costs:

Total complexity:

• Practice

ZOJ 2112 Dynamic Rankings