A common question arises: what distinguishes a Chairman Tree from a Persistent Segment Tree? The answer lies in their definitions—a Chairman Tree is specifically a persistent weighted segment tree, which is a specialized application of the persistent segment tree structure.

Definition

A persistent segment tree is a data structure that preserves access to all historical versions of the tree after modifications, enabling queries and modifications on any previous version.

Core Principle

A fundamental theorem guides our implementation:

Space complexity will never exceed time complexity.

This means we need not copy the entire segment tree for each operation. Instead, during version updates, we only duplicate the nodes along the access path, re-establish parent-child relationships, and update values accordingly. This approach can be summarized as the Triple-Step Method: copy nodes, reset links, update values.

Basic Implementation

Below demonstrates a persistent segment tree supporting point updates and range queries:

struct PersistentSegTree {
    int leftChild[MAX_NODES], rightChild[MAX_NODES];
    int nodeSum[MAX_NODES], roots[MAX_VERSIONS];
    int nodeCount;

    int createNode() {
        nodeCount++;
        leftChild[nodeCount] = rightChild[nodeCount] = 0;
        nodeSum[nodeCount] = 0;
        return nodeCount;
    }

    int construct(int low, int high) {
        int nodeId = createNode();
        if (low == high) return nodeId;
        int mid = (low + high) >> 1;
        leftChild[nodeId] = construct(low, mid);
        rightChild[nodeId] = construct(mid + 1, high);
        return nodeId;
    }

    int modify(int prevNode, int low, int high, int position) {
        // Step 1: Copy the node
        int newNode = createNode();
        leftChild[newNode] = leftChild[prevNode];
        rightChild[newNode] = rightChild[prevNode];
        nodeSum[newNode] = nodeSum[prevNode] + 1;

        if (low == high) return newNode;

        int mid = (low + high) >> 1;
        // Step 2: Reset links
        if (position <= mid)
            leftChild[newNode] = modify(leftChild[newNode], low, mid, position);
        else
            rightChild[newNode] = modify(rightChild[newNode], mid + 1, high, position);
        // Step 3: Update values
        nodeSum[newNode] = nodeSum[leftChild[newNode]] + nodeSum[rightChild[newNode]];
        return newNode;
    }

    int findKth(int nodeId, int low, int high, int rank) {
        if (low == high) return low;
        int leftCount = nodeSum[leftChild[nodeId]];
        int mid = (low + high) >> 1;
        if (rank <= leftCount)
            return findKth(leftChild[nodeId], low, mid, rank);
        else
            return findKth(rightChild[nodeId], mid + 1, high, rank - leftCount);
    }
} pst;

Permanent Lazy Propagation

For range updates and range queries, lazy propagation is typically employed. However, standard pushdown operations would modify historical versions, corrupting past data. Creating new nodes during every pushdown would lead to excessive memory consumption.

The solution is permanent lazy tags: eliminate pushdown entirely and account for lazy tag contributions during query calculations.

struct PersistentSegTreeRange {
    int lChild[MAX_NODES], rChild[MAX_NODES];
    int segLeft[MAX_NODES], segRight[MAX_NODES];
    int treeSum[MAX_NODES], versionRoots[MAX_VERSIONS];
    int lazyTag[MAX_NODES];
    int totalNodes;

    int allocateNode() {
        totalNodes++;
        lChild[totalNodes] = rChild[totalNodes] = 0;
        treeSum[totalNodes] = lazyTag[totalNodes] = 0;
        segLeft[totalNodes] = segRight[totalNodes] = 0;
        return totalNodes;
    }

    void recalculate(int node, int left, int right) {
        treeSum[node] = treeSum[lChild[node]] + treeSum[rChild[node]]
                        + lazyTag[node] * (right - left + 1);
    }

    int buildTree(int left, int right, int values[]) {
        int node = allocateNode();
        segLeft[node] = left;
        segRight[node] = right;
        if (left == right) {
            treeSum[node] = values[left];
            return node;
        }
        int mid = (left + right) >> 1;
        lChild[node] = buildTree(left, mid, values);
        rChild[node] = buildTree(mid + 1, right, values);
        recalculate(node, left, right);
        return node;
    }

    int rangeUpdate(int prevNode, int queryLeft, int queryRight, int delta) {
        int newNode = allocateNode();
        lChild[newNode] = lChild[prevNode];
        rChild[newNode] = rChild[prevNode];
        segLeft[newNode] = segLeft[prevNode];
        segRight[newNode] = segRight[prevNode];
        lazyTag[newNode] = lazyTag[prevNode];
        treeSum[newNode] = treeSum[prevNode];

        if (segLeft[newNode] == queryLeft && segRight[newNode] == queryRight) {
            treeSum[newNode] += delta * (queryRight - queryLeft + 1);
            lazyTag[newNode] += delta;
            return newNode;
        }

        int mid = (segLeft[newNode] + segRight[newNode]) >> 1;
        if (queryRight <= mid)
            lChild[newNode] = rangeUpdate(lChild[newNode], queryLeft, queryRight, delta);
        else if (queryLeft > mid)
            rChild[newNode] = rangeUpdate(rChild[newNode], queryLeft, queryRight, delta);
        else {
            lChild[newNode] = rangeUpdate(lChild[newNode], queryLeft, mid, delta);
            rChild[newNode] = rangeUpdate(rChild[newNode], mid + 1, queryRight, delta);
        }
        recalculate(newNode, segLeft[newNode], segRight[newNode]);
        return newNode;
    }

    int rangeQuery(int node, int queryLeft, int queryRight) {
        if (segLeft[node] == queryLeft && segRight[node] == queryRight)
            return treeSum[node];

        int mid = (segLeft[node] + segRight[node]) >> 1;
        int result = lazyTag[node] * (queryRight - queryLeft + 1);

        if (queryRight <= mid)
            result += rangeQuery(lChild[node], queryLeft, queryRight);
        else if (queryLeft > mid)
            result += rangeQuery(rChild[node], queryLeft, queryRight);
        else {
            result += rangeQuery(lChild[node], queryLeft, mid);
            result += rangeQuery(rChild[node], mid + 1, queryRight);
        }
        return result;
    }
} pstRange;

Practical Applications

Range K-th Element Query

One of the most common applications is the Chairman Tree approach, which combines coordinate compression with value domain maintenance. By sequentially inserting n elements into the persistent structure, we can query the k-th smallest element in any range by examining whether the count in the left subtree meets the rank requirement, then traversing left or right accordingly.

This technique effectively supersedes Mo's Algorithm for many scenarios, offering superior time complexity, though it requires deeper understanding and more careful debugging.

Historical Version Queries

The ability to query any historical version is the inherent capability of persistent data structures, making it straightforward to answer questions about past states of the data.