El Árbol de Chtholly es una estructura de datos basada en conjuntos que facilita la manipulación eficiente de intervalos, comúnmente utilizada en problemas de programación competitiva. Su diseño se centra en dos operaciones fundamentales: división y cobertura, que permitne gestionar rangos de valores con complejidad amortizada.

La operación de división, denominada Split, segmenta un intervalo en dos partes en una posición dada, devolviendo un iterador al subintervaol resultante. A continuación se presenta una implementación revisada con nombres de variables modificados:

// Estructura para representar nodos de intervalo
struct Segment {
    int leftEndpoint, rightEndpoint;
    mutable int value;  // mutable permite modificación a través de iteradores
    Segment(int L, int R = -1, int V = 0) : leftEndpoint(L), rightEndpoint(R), value(V) {}
    bool operator<(const Segment& other) const { return leftEndpoint < other.leftEndpoint; }
};

// Función de división: parte un intervalo en la posición 'pos'
Iterator splitAt(int pos) {
    Iterator it = dataStructure.lower_bound(Segment(pos));
    if (it != dataStructure.end() && it->leftEndpoint == pos) return it;
    --it;
    int start = it->leftEndpoint, end = it->rightEndpoint, val = it->value;
    dataStructure.erase(it);
    dataStructure.insert(Segment(start, pos - 1, val));
    return dataStructure.insert(Segment(pos, end, val)).first;
}

La operación de cobertura, denominada Cover, reemplaza todos los intervalos en un rango específico con un nuevo valor, reduciendo el número total de intervalos y garantizando una complejidad amortizada favorable. Esta es la clave para el rendimiento del árbol.

void coverRange(int l, int r, int newValue) {
    Iterator endIter = splitAt(r + 1), startIter = splitAt(l);
    dataStructure.erase(startIter, endIter);
    dataStructure.insert(Segment(l, r, newValue));
}

Para demostrar su aplicación, se resuelve el problema CF896C con una solución reestructurada. El código siguiente incluye funciones auxiliares para suma, rango y consulta, con ajustes en la lógica y nomenclatura:

#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Interval {
    int start, end;
    mutable int data;
    Interval(int s, int e = -1, int d = 0) : start(s), end(e), data(d) {}
    bool operator<(const Interval& other) const { return start < other.start; }
};

set<interval> intervalSet;
using Iter = set<interval>::iterator;

Iter splitInterval(int pos) {
    Iter it = intervalSet.lower_bound(Interval(pos));
    if (it != intervalSet.end() && it->start == pos) return it;
    --it;
    int s = it->start, e = it->end, d = it->data;
    intervalSet.erase(it);
    intervalSet.insert(Interval(s, pos - 1, d));
    return intervalSet.insert(Interval(pos, e, d)).first;
}

void coverInterval(int l, int r, int val) {
    Iter endIt = splitInterval(r + 1), startIt = splitInterval(l);
    intervalSet.erase(startIt, endIt);
    intervalSet.insert(Interval(l, r, val));
}

void addToRange(int l, int r, int addend) {
    Iter endIt = splitInterval(r + 1), startIt = splitInterval(l);
    for (auto it = startIt; it != endIt; ++it) {
        it->data += addend;
    }
}

int findKthSmallest(int l, int r, int k) {
    Iter endIt = splitInterval(r + 1), startIt = splitInterval(l);
    vector<pair int="">> segments;
    for (auto it = startIt; it != endIt; ++it) {
        segments.emplace_back(it->data, it->end - it->start + 1);
    }
    sort(segments.begin(), segments.end());
    for (const auto& seg : segments) {
        k -= seg.second;
        if (k <= 0) return seg.first;
    }
    return -1;
}

int queryPowerSum(int l, int r, int exponent, int modulo) {
    Iter endIt = splitInterval(r + 1), startIt = splitInterval(l);
    int result = 0;
    for (auto it = startIt; it != endIt; ++it) {
        int count = it->end - it->start + 1;
        int powerVal = 1;
        for (int i = 0; i < exponent; ++i) powerVal = (powerVal * it->data) % modulo;
        result = (result + count * powerVal) % modulo;
    }
    return result;
}

// Ejemplo de uso simplificado
int main() {
    // Inicialización y procesamiento de operaciones según el problema
    return 0;
}
</pair></interval></interval></cmath></algorithm></vector></set>