比如找到区间最左边 $<k$ 的数。

int search(int u, int l, int k) {
        //Find the first element < k in [l, r]
        if(lc[u] == rc[u]) {
            if(minn[u] >= k) return -1;
            return lc[u];
        }
        if(minn[u] >= k) return -1;
        if(rc[u] < l) return -1;
        int res = search(u << 1, l, k);
        if(res != -1) return res;
        return search(u << 1 | 1, l, k);
    }

网上大部分代码都形如这样，没有对其复杂度做出解释，毕竟这玩意会左右两区间都遍历，本人对其复杂度感到质疑。