Fenwick Binary Lifting Find Kth

Problem

Find the position of the k-th cumulative frequency using binary lifting on a Fenwick tree.

initial holds starting frequencies. operations contains ["update", i, delta] (add delta at index i) or ["kth", k] (smallest 0-based index whose prefix sum is at least k). Walking powers of two from the highest bit locates the answer in O(log n).

Return the answers, or -1 when the total frequency is less than k.

Hint

The binary lifting pointer tracks how many elements have been consumed so far.

Test cases

case 1

in: [[1,3,2,4],[["kth",1],["kth",4],["kth",8],["update",1,5],["kth",9]]]

expected: [0,1,3,1]

case 2

in: [[1],[["kth",2]]]

expected: [-1]

case 3

in: [[0,0,1],[["kth",1]]]

expected: [2]

case 4

in: [[2,2],[["kth",2],["kth",3],["kth",4],["kth",5]]]

expected: [0,1,1,-1]

Starter codePython

def fenwick_kth_ops(initial, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor