Árboles de Segmentos (V): Búsqueda binaria o "Walking"

Consideremos el siguiente problema: tenemos una secuencia $a_1, a_2, \ldots, a_n$ de números y debemos soportar $q$ consultas de los siguientes tipos:

1. Dados $l$, $r$ y $x$, suma $x$ a todos los elementos de la secuencia en $[l, r]$. 
2. Dado $k$, encuentra el menor índice $i$ tal que $a_i \geq k$ o determina que no existe tal índice.

En el manual anterior se vio como soportar el primer tipo de consultas y obtener el máximo en un rango usando árboles de segmentos. Con estas dos operaciones, ya podemos llegar a una solución bastante rápida. Para cada consulta de tipo $2$, se puede realizar una búsqueda binaria del menor índice $i$ tal que el máximo en el rango $[1, i]$ es al menos $k$, o determinar si el máximo de todo el arreglo es menor a $k$ (y por tanto no hay solución). Esta solución tendría una complejidad de $O(q \log^2 n)$, puesto que para cada consulta se hacen $O(\log n)$ operaciones de obtener el máximo, con una complejidad por operación de $O(\log n)$.

Aunque esta solución ya es bastante rápida, existe una manera de reducir la complejidad a $O(q \log n)$ (aunque pueda parecer una optimización pequeña, puede ser bastante significativa en algunos problemas) con una técnica conocida cómo "caminar" o "descender" por el árbol de segmentos (en inglés normalmente se la conoce por "walking"). Esta técnica consiste en hacer la búsqueda binaria directamente dentro del árbol de segmentos. Esencialmente, los hijos de cada nodo ya dividen el rango en dos, pues esta es la propiedad básica del árbol de segmentos, por lo que podemos interpretar descender por el árbol como otra manera de hacer búsqueda binaria, dividiendo consecutivamente el intervalo de posibilidades en dos. Para ello, si estamos en un nodo descenderemos al hijo izquierdo (que cubre un rango de índices menores al derecho) si y solo si el máximo en su rango es $\geq k$. En caso contrario, descenderemos al hijo derecho. De esta manera, estamos efectivamente visitando rangos que contengan el menor índice con $a_i \geq k$ y que se reducen en tamaño por un factor de $2$. Finalmente, acabaremos llegando a una hoja del árbol de segmentos y simplemente necesitaremos comprobar que el valor de esa hoja es al menos $k$ y devolver el índice. También podría ser que el valor de la hoja sea $< k$, y entonces tendríamos que decir que no existe tal índice.

Para analizar la complejidad la clave es que el valor máximo en el rango cubierto por un nodo ya está precalculado, por lo que se puede determinar en $O(1)$ el valor máximo del hijo izquierdo para saber si descender a él. Por lo tanto, para cada consulta visitamos $O(\log n)$ nodos, ya que la altura del árbol de segmentos es $O(\log n)$, y las operaciones que hacemos en cada nodo son de complejidad constante, por lo que la complejidad final es $O(q \log n)$.

El código sería el siguiente: 

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

struct segTree{
    vector<int> mx, upd;
    int sz;
    void init(int n){
        sz = 1;
        while(sz < n) sz *= 2;
        mx.assign(2 * sz, -INF);
        upd.assign(2 * sz, 0);
    }
    void push(int x){
        mx[2 * x + 1] += upd[x];
        upd[2 * x + 1] += upd[x];
        mx[2 * x + 2] += upd[x];
        upd[2 * x + 2] += upd[x];
        upd[x] = 0;
    }
    void add(int l, int r, int val, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            mx[x] += val;
            upd[x] += val;
            return;
        }else if(lx >= r || rx <= l) return;
        int m = (lx + rx) / 2;
        push(x);
        add(l, r, val, 2 * x + 1, lx, m);
        add(l, r, val, 2 * x + 2, m, rx);
        mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
    }
    void add(int l, int r, int val){
        add(l, r, val, 0, 0, sz);
    }

    //Aquí empieza la parte que se ha explicado en este manual.
    int walk(int x, int lx, int rx, int k){
        if(rx - lx == 1){
            //Puesto que los intervalos son de la forma [lx, rx), aquí estamos ya en una hoja del árbol.
            if(mx[x] >= k) return lx;
            else return -1; //No hay ningún valor en el arreglo >= k.
        }
        int m = (lx + rx) / 2;
        push(x);
        if(mx[2 * x + 1] >= k) return walk(2 * x + 1, lx, m, k); //Priorizamos el hijo izquierdo.
        else return walk(2 * x + 2, m, rx, k);
    }
    int walk(int k){
        return walk(0, 0, sz, k);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    segTree st; st.init(n);
    for(int i = 0; i < n; i++){
        int h; cin >> h;
        st.add(i, i+1, INF + h); //Sumamos INF porque inicialmente el valor es -INF.
    }
    while(q--){
        int r; cin >> r;
        int ind = st.walk(r);
        if(ind >= 0) st.add(ind, ind+1, -r);
        cout << ind + 1 << " ";
    }
    cout << "\n";
}

El código ha sido probado en este problema, que es igual al ya explicado pero sin suma en rango.

Nótese que la técnica explicada en este artículo tiene más aplicaciones además de la de resolver el problema comentado, pues la búsqueda binaria en el árbol se puede presentar de muchas formas. Otra muy famosa es contar el $k$-ésimo cero en un arreglo.