#include<deque>
 
struct PersistentSegmentTree {
    struct Node {
        long long value = 0;
        
        Node* lch = 0;
        Node* rch = 0;
    };
    int n;
    std::deque<Node> nodes;
    
    PersistentSegmentTree(int nsize) {
        n = 1;
        while(n < nsize) {
            n *= 2;
        }
        nodes.resize(2*n);
        for(int i=n-1; i>0; i--) {
            nodes[i].lch = &nodes[2*i];
            nodes[i].rch = &nodes[2*i+1];
        }
    }
    
    Node* set(int pos, int to_set, Node* node, int lb = 0, int rb = -1) {
        // [lb, rb) represents the range of the current node
        
        if(rb == -1) rb = n;
        
        nodes.push_back(*node);  // Create a new version of the node
        Node* cur = &nodes.back();
        
        if(rb - lb == 1) {  // We are at leaf, so perform the set
            cur->value = to_set;
            return cur;
        }
        int mid = (lb + rb) / 2;
        if(pos < mid) {
            cur->lch = set(pos, to_set, cur->lch, lb, mid);  // Recursive call on left subtree
        } else {
            cur->rch = set(pos, to_set, cur->rch, mid, rb);  // Recursive call on right subtree
        }
        cur->value = cur->lch->value + cur->rch->value;
        return cur;  // Return the new version of the node.
    }
    
    long long get(int l, int r, Node* cur, int lb = 0, int rb = -1) {
        // [lb, rb) represents the range of the current node
        
        if(rb == -1) rb = n;
        
        if(l <= lb && rb <= r) {  // Segment of the node is fully within the queried range
            return cur->value;
        }
        int mid = (lb + rb) / 2;
        long long result = 0;
        if(l < mid) {
            result += get(l, r, cur->lch, lb, mid);  // Recursive call on left subtree
        }
        if(mid < r) {
            result += get(l, r, cur->rch, mid, rb);  // Recursive call on right subtree
        }
        return result;
    }
};

int main() {
    PersistentSegmentTree stree(10);
    std::deque<PersistentSegmentTree::Node*> root_versions = {&stree.nodes[1]};  // Track tree root versions
    root_versions.push_back(stree.set(3, 5, root_versions.back()));  // Set a value
    root_versions.push_back(stree.set(4, 6, root_versions.back()));  // Set a value
    root_versions.push_back(stree.set(5, 7, root_versions.back()));  // Set a value
    int range_sum = stree.get(2, 7, root_versions[root_versions.size()-2]);  // Query range before the last operation
}