能否在隐式Treap中实现O(logN)复杂度的LTE/第k小区间查询？

现有隐式Treap的功能 #

隐式Treap是一种支持多种**O(logN)**时间复杂度区间操作的数据结构，当前实现支持以下操作：

• 在指定位置插入值
• 删除指定位置的元素
• 修改指定位置的值
• 给区间内每个元素加一个常数
• 将区间内每个元素设为某个常数
• 查询区间的和/最小值/最大值

待扩展的操作疑问 #

现询问：能否在隐式Treap中以**O(logN)**或低于区间大小的时间复杂度实现以下操作？

• 统计区间内小于等于指定值的元素数量（即LTE操作）
• 查询区间内第k小元素（即kthSmallest操作）

Wavelet Tree、可持久化线段树等数据结构可实现上述LTE/第k小操作，但这类结构不支持隐式Treap具备的插入、删除、区间赋值、区间加法等操作，无法单独维护此类结构来满足需求。

LTE与第k小操作示例 #

arr = [2, 3, 1, 5, 2, 3]
// arr.LTE(1, 5, 2) == 2 ，因为位置1到5的元素是3, 1, 5, 2, 3，其中只有1和2 ≤ 2
// arr.kth(0, 4, 2) == 2 ，因为位置0到4的元素是2, 3, 1, 5, 2，排序后为1, 2, 2, 3, 5，第2小的元素是2

当前C++隐式Treap实现示例 #

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

输出结果 #

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 

已尝试的思路 #

我曾尝试借鉴可持久化线段树的思路，用可持久化Treap实现上述LTE/第k小操作，但未找到可行方案——不过该思路仍有可能成立。

内容的提问来源于stack exchange，提问作者rokkc