Common Implementation Challenges

When implementing Splay trees for interval operations, developers often encounter subtle bugs. Below are critical fixes and a production-ready template.

Key Error Fixes

Incorrect size comparison in find operation:

int find_node(int k) {
    int current = root;
    while (true) {
        push_down(current);
        int left_size = size[child[current][0]];
        if (k <= left_size) {
            current = child[current][0];
            continue;
        }
        k -= left_size + 1;
        if (k > 0) {
            current = child[current][1];
            continue;
        }
        break;
    }
    return current;
}

Incorrect subtree access during split operations:

void split(int node, int target) {
    splay(node, 0);
    splay(target, node);
    // Corrected: Accessing left subtree of right child
    int subtree_root = child[node][1];
    if (subtree_root) {
        int left_child = child[subtree_root][0];
        // ...rest of implementation
    }
}

Production Template

Complete template supporting interval reversal, value assignment, sum queries, and memory management:

// Constants and structures
const int MAXN = 100005;
int child[MAXN][2], parent[MAXN], size[MAXN];
int sum[MAXN], left_max[MAXN], right_max[MAXN], global_max[MAXN];
bool tag_assign[MAXN], tag_reverse[MAXN];
int free_list[MAXN], free_count;

// Memory management
int get_node() {
    return free_count ? free_list[--free_count] : ++node_count;
}

// Rotation implementation
void rotate(int node) {
    int p = parent[node], gp = parent[p];
    bool is_left = (child[p][1] == node);
    parent[node] = gp;
    if (gp) child[gp][child[gp][1] == p] = node;
    child[p][is_left] = child[node][!is_left];
    if (child[node][!is_left]) parent[child[node][!is_left]] = p;
    child[node][!is_left] = p;
    parent[p] = node;
    update(p);
}

// Splay with stack-based pushdown
void splay(int node, int target) {
    int stack[MAXN], sp = 0;
    for (int cur = node; cur != target; cur = parent[cur])
        stack[++sp] = cur;
    while (sp) push_down(stack[sp--]);
    for (int p = parent[node]; p != target; rotate(node), p = parent[node])
        if (parent[p] != target) 
            rotate((child[parent[p]][1] == p) == (child[p][1] == node) ? p : node);
    update(node);
    if (target == 0) root = node;
}

// Core operations
void update(int node) {
    int left = child[node][0], right = child[node][1];
    size[node] = size[left] + size[right] + 1;
    sum[node] = val[node] + sum[left] + sum[right];
    left_max[node] = max(left_max[left], sum[left] + val[node] + left_max[right]);
    right_max[node] = max(right_max[right], sum[right] + val[node] + right_max[left]);
    global_max[node] = max({global_max[left], global_max[right], 
                          right_max[left] + val[node] + left_max[right]});
}

void assign_value(int node, int value) {
    if (!node) return;
    tag_assign[node] = true;
    val[node] = value;
    sum[node] = size[node] * value;
    if (value <= 0) {
        left_max[node] = right_max[node] = 0;
        global_max[node] = value;
    } else {
        left_max[node] = right_max[node] = global_max[node] = sum[node];
    }
}

void reverse_subtree(int node) {
    if (!node) return;
    tag_reverse[node] ^= true;
    swap(child[node][0], child[node][1]);
    swap(left_max[node], right_max[node]);
}