[Tutorial] Find the kth element in an array with update query in O(n)

Правка en3, от quanlt206, 2022-07-09 11:09:43

Problems

Give an array consists N integers and Q queries, with two types :

  1. ? k -> print the kth element in this array.
  2. ! k -> remove the kth element in this array.

a[i] <= 1e9 N, Q <= 2e5

This problem likes "List Removal" problems on Cses (here)

Naive Approach

Using brute-force, query 1 will be processed in O(1), query 2 will be processed in O(n).

Code:

void Query_1(int k) {
    cout<<a[k]<<" ";
}
void Query_2(int k) {
    for (int i = k; i < n; i++) a[i] = a[i + 1];
    n--;
}

O(nlog(n)log(n)) using IT, BIT

Because using IT(Segment Tree) and BIT is the same, so now I talking about IT.

Firstly, we will have an array B, B[i] = 1 if ith element not deleted yet, B[i] = 0 otherwise. We will build a Segment Tree whose each node has 1 value, it is the sum B[i] in [L, R].

Now, we can find the kth element in the array easily by binary search. Code:

int Find(int k) {
    int l = 1, r = n, mid, res;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (GetSum(1, mid) >= k) { 
            res = mid;
            r = mid - 1; 
        }
        else l = mid + 1;
    }
    return res;
}

Because the complexity of GetSum(1, x) is O(log(n)), complexity of binary search is O(log(n)), so Find(k) is O(log(n)^2), total complexity is O(nlog(n)log(n)) or O(nlog(n)^2)).

O(nlogn), using ordered_set ------------------

This problem can solve very easily by ordered_set: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

Using Trie, O(n) complexity

[](https://www.geeksforgeeks.org/trie-insert-and-search/) This is for people who don't know Trie.

The main idea is inserting all index in array into Trie. Firstly, we will converse all index to string, and all string has the same length (we will insert "0" before some strings). Now the problem is find the Kth string (lexicographically) smallest in Trie.

We will build a Trie, each node like :

struct Node {
    Node* child[10];
    int cnt, val;
    Node() {
        for (int i = 0; i < 10; i++) child[i] = NULL;
        cnt = val = 0;
    }
};
  • cnt : numbers of string pass this node
  • val : if this Node is the end of a string (index), val = a[index].

Okay, now we will find the way to reach the Kth smallest string (lexicographically).

Consider we

We will have Trie like :

Теги #trie

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский quanlt206 2022-07-10 11:41:57 9 Tiny change: 'ie, O(nlog(max(k))) complexi' -> 'ie, O(nlogn) complexi'
en14 Английский quanlt206 2022-07-10 11:31:23 9
en13 Английский quanlt206 2022-07-10 04:17:13 7
en12 Английский quanlt206 2022-07-09 17:51:04 12 Tiny change: ' Trie, O(n) complexi' -> ' Trie, O(nlog(max(k))) complexi'
en11 Английский quanlt206 2022-07-09 17:44:29 34
en10 Английский quanlt206 2022-07-09 16:14:47 59 (published)
en9 Английский quanlt206 2022-07-09 16:13:46 89
en8 Английский quanlt206 2022-07-09 16:12:39 20
en7 Английский quanlt206 2022-07-09 16:11:10 88
en6 Английский quanlt206 2022-07-09 16:09:10 4
en5 Английский quanlt206 2022-07-09 16:08:15 7802
en4 Английский quanlt206 2022-07-09 15:52:59 536
en3 Английский quanlt206 2022-07-09 11:09:43 251
en2 Английский quanlt206 2022-07-09 08:27:43 2271
en1 Английский quanlt206 2022-07-09 07:27:15 277 Initial revision (saved to drafts)