Overview

Chtholly Tree is a data structure that manages intervals using a set with amortized complexity based on randomization and assign operations.

Core Principles

The structure maintains disjoint intervals in a sorted set, where each element represents a contiguous range. Intervals are ordered by their left endpoints, and their union covers the entire domain [1, n].

Initialization

Typically initialized by inserting individual element intervals:

for (int i = 1; i <= n; i++) {
    initialValues[i] = (randomGen() % maxVal) + 1;
    intervalSet.insert(Interval(i, i, initialValues[i]));
}

Key Operations

Interval Splitting

The split operation divides an enterval containing a given position:

set<Interval>::iterator splitAt(int position) {
    auto it = intervalSet.lower_bound(Interval(position));
    if (it != intervalSet.end() && it->start == position) {
        return it;
    }
    it--;
    Interval current = *it;
    intervalSet.erase(it);
    intervalSet.insert(Interval(current.start, position - 1, current.value));
    return intervalSet.insert(Interval(position, current.end, current.value)).first;
}

Range Assignment

Assigns a value to a entire interval, merging overlapping segments:

void assignRange(int left, int right, long long value) {
    auto rightIt = splitAt(right + 1);
    auto leftIt = splitAt(left);
    intervalSet.erase(leftIt, rightIt);
    intervalSet.insert(Interval(left, right, value));
}

Range Updates

Apply operations to all interval within a range:

void modifyRange(int left, int right, long long delta) {
    auto rightIt = splitAt(right + 1);
    auto leftIt = splitAt(left);
    for (auto it = leftIt; it != rightIt; it++) {
        it->value += delta;
    }
}

K-th Smallest Query

Find the k-th smallest value in a range:

long long findKthSmallest(int left, int right, int k) {
    vector<pair<long long, int>> values;
    auto rightIt = splitAt(right + 1);
    auto leftIt = splitAt(left);
    
    for (auto it = leftIt; it != rightIt; it++) {
        values.push_back({it->value, it->end - it->start + 1});
    }
    
    sort(values.begin(), values.end());
    for (auto &[val, count] : values) {
        k -= count;
        if (k <= 0) return val;
    }
    return -1;
}

Complete Implementation Example

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

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

set<Interval> intervalSet;

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

// Split and other operation implementations as shown above

int main() {
    // Implementation details for specific problem context
    return 0;
}