Introduction

The Chtholly Tree, often referred to as the Old Driver Tree (ODT), is a data structure optimized for specific scenarios involving sequence operations. It is particularly effective when problems feature range assignment operations and randomly generated data. The core principle involves decomposing a sequence into contiguous intervals where all elements with in a specific interval share the same value. These intervals are managed and ordered using a balanced binary search tree, typically C++'s std::set.

While the structure relies heavily on brute-force iteration over intervals, the randomization of data and range assignments ensures that the number of intervals remains small, yielding an expected time complexity of approximately O(n log n) or better for many operations. This approach is not a general-purpose replacement for segment trees but serves as a powerful heuristic in specific competitive programming contexts.

Prerequisites

Implementing the Chtholly Tree requires familiarity with C++'s Standard Template Library (STL), specifically the std::set container. Key operations include:

• insert(x): Inserts an element into the set.
• erase(iterator): Removes an element at the specified iterator position.
• erase(first, last): Removes a range of elements [first, last).
• lower_bound(x): Returns an iterator to the first element not less than x.

Data Structure and Initialization

First, we define a structure to represent a continuous interval. This structure must store the left boundary, right boundary, and the value assigned to that interval. To allow modification of values while the structure resides inside a set, the value field must be declared as mutable.

struct Interval {
    int left, right;
    mutable long long value;

    Interval(int l, int r = -1, long long v = 0) : left(l), right(r), value(v) {}

    bool operator<(const Interval& other) const {
        return left < other.left;
    }
};

std::set<Interval> tree;

Initialization involves inserting each index as a separate interval. A sentinel interval is typically added at the end to prevent out-of-bounds errors during boundary splits.

void build(int n, const std::vector<long long>& data) {
    for (int i = 0; i < n; ++i) {
        tree.insert(Interval(i, i, data[i]));
    }
    // Sentinel node to prevent iterator issues
    tree.insert(Interval(n, n, 0));
}

Core Operations

The efficiency of the Chtholly Tree depends on two primary functions: dividing an interval and assigning a value to a range.

1. Split Operation

The split(pos) function ensures that there is an interval starting exactly at pos. If an interval currently spans across pos, it is severed into two distinct intervals: [l, pos-1] and [pos, r]. The function returns an iterator to the interval starting at pos.

using Iterator = std::set<Interval>::iterator;

Iterator split(int pos) {
    // Find the first interval with left >= pos
    Iterator it = tree.lower_bound(Interval(pos));
    
    // If an interval already starts at pos, return it
    if (it != tree.end() && it->left == pos) {
        return it;
    }
    
    // Otherwise, move back to the interval containing pos
    --it;
    int start = it->left, end = it->right;
    long long val = it->value;
    
    // Remove the original interval
    tree.erase(it);
    
    // Insert the split parts
    tree.insert(Interval(start, pos - 1, val));
    // Return iterator to the new right part
    return tree.insert(Interval(pos, end, val)).first;
}

2. Range Assignment

The assign(l, r, val) operasion assigns a single value val to every element in the range [l, r]. This is the optimization driver for the data structure. It cleanly removes all intervals in the target range and replaces them with a single, merged interval.

void assign_range(int l, int r, long long val) {
    // Note the order: split r+1 first, then l
    Iterator end_itr = split(r + 1);
    Iterator start_itr = split(l);
    
    // Erase all intervals between l and r
    tree.erase(start_itr, end_itr);
    
    // Insert the new unified interval
    tree.insert(Interval(l, r, val));
}

Practical Example: Randomized Operations

To demonstrate the utility of the Chtholly Tree, we will solve a problem similar to Codeforces 896C. The task involves handling four types of operations on a sequence of length n:

1. Add: Add x to every element in range [l, r].
2. Assign: Set every element in range [l, r] to x.
3. K-th: Find the k-th smallest element in range [l, r].
4. Power Sum: Calculate the sum of the x-th power of elements in [l, r] modulo y.

Implementation Details

1. Range AdditionWe split the range [l, r] and iterate through the resulting intervals, adding the value x to each.

void add_range(int l, int r, long long x) {
    Iterator end_itr = split(r + 1);
    Iterator start_itr = split(l);
    
    for (Iterator it = start_itr; it != end_itr; ++it) {
        it->value += x;
    }
}

2. K-th ElementWe extract all interval within [l, r] into a vector. Since the Chtholly Tree intervals have uniform values, we sort these intervals by their value and scan them to find the element at rank k.

long long find_kth(int l, int r, long long k) {
    std::vector<std::pair<long long, int>> segments;
    
    Iterator end_itr = split(r + 1);
    Iterator start_itr = split(l);
    
    for (Iterator it = start_itr; it != end_itr; ++it) {
        segments.emplace_back(it->value, it->right - it->left + 1);
    }
    
    std::sort(segments.begin(), segments.end());
    
    for (const auto& seg : segments) {
        k -= seg.second;
        if (k <= 0) {
            return seg.first;
        }
    }
    return -1; // Not found
}

3. Power SumIterate through the intervals in [l, r]. For each interval, calculate value^p % mod, multiply by the interval length, and accumulate the result.

long long fast_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long calc_power_sum(int l, int r, long long x, long long mod) {
    Iterator end_itr = split(r + 1);
    Iterator start_itr = split(l);
    
    long long total = 0;
    for (Iterator it = start_itr; it != end_itr; ++it) {
        int len = it->right - it->left + 1;
        long long term = fast_pow(it->value, x, mod);
        total = (total + term * len) % mod;
    }
    return total;
}

Complexity Analysis

The time complexity of this structure is non-deterministic in the worst case but highly efficient on random data. The assign_range operation reduces the number of nodes in the set by merging intervals. As long as the data is sufficiently random or there are enough range assignments to prevent the interval count from ballooning, each operation runs in an expected O(log n) for set access plus O(m) for iterating over the affected intervals, where m is the number of intervals in the range, which tends to be small.