LTE/kth Smallest Operations in an Implicit Treap

Question

An implicit treap is a data structure that allows several types of range operations in O(logN) time. For example, the following types of queries are supported in my implementation all in O(logN) time:

• insert value at position
• remove element at position
• change value at position
• add a constant value to each element in a range
• set each element in a range to a constant value
• get the sum/min/max of a range

I was wondering if it's possible to also perform the following operations on an implicit treap in O(logN) time or a lower than O(range size) time complexity:

• get the number of elements in a range less than or equal to a value (this value is taken as input to the LTE function)
• get the kth smallest element in a range (k is taken as input to the kthSmallest function)

These LTE/kth smallest operations can be implemented with data structures like Wavelet Trees and Persistent Segment Trees, but these data structures don't support the insertions/deletions/range set/range add operations that implicit treaps do, so we can't just keep a separate data structure to manage these operations.

Here is a sample input and output that clarifies the LTE and kth smallest operations:

arr = [2, 3, 1, 5, 2, 3]
// arr.LTE(1, 5, 2) == 2 b/c the elements from positions 1 to 5 are 3, 1, 5, 2, 3 and only 1 and 2 are <= 2
// arr.kth(0, 4, 2) == 2 b/c the elements from positions 0 to 4 are 2, 3, 1, 5, 2 and the values ordered at 1, 2, 2, 3, 5. The second smallest value is 2.

This is the current usage of my implicit treap implementation in C++:

int main() {
    ImplicitTreap treap;
    treap.insert(0, 5);
    treap.insert(1, 3);
    treap.insert(2, 7);
    treap.insert(3, 9);
    cout << "Initial treap: ";
    treap.print();
    cout << "Size: " << treap.size() << endl;
    treap.addRange(1, 2, 2);
    cout << "After adding 2 to range [1,2]: ";
    treap.print();
    treap.setRange(0, 1, 10);
    cout << "After setting range [0,1] to 10: ";
    treap.print();
    cout << "Range sum [0,2]: " << treap.rangeSum(0, 2) << endl;
    cout << "Range min [1,3]: " << treap.rangeMin(1, 3) << endl;
    cout << "Range max [1,3]: " << treap.rangeMax(1, 3) << endl;
    treap.updateValue(2, 4);
    cout << "After updating position 2 to 4: ";
    treap.print();
    treap.erase(1);
    cout << "After erasing position 1: ";
    treap.print();
    return 0;
}

This is the output:

Initial treap: 5 3 7 9 
Size: 4
After adding 2 to range [1,2]: 5 5 9 9 
After setting range [0,1] to 10: 10 10 9 9 
Range sum [0,2]: 29
Range min [1,3]: 9
Range max [1,3]: 10
After updating position 2 to 4: 10 10 4 9 
After erasing position 1: 10 4 9 

I've tried exploring using a persistent treap to do these LTE/kth smallest operations similar to how a persistent segment tree is used, but I couldn't figure out how to make this work (though the persistent treap strategy may still work)