Problem 14: Persistent Segment Tree

Problem Statement: Implement a persistent segment tree to answer range sum queries over different versions of an array.

Input

First line contains n and q. Next line contains n integers. Then q queries follow. Each query: version, l, r.

Output

For each query, print the range sum for the given version.

Examples


Input:
5 3\n1 2 3 4 5\n0 1 3\n1 2 5\n0 1 5

Output:
6\n14\n15

Solution in C++


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

struct Node{
    int sum;
    Node *left, *right;
    Node(int sum, Node* left, Node* right): sum(sum), left(left), right(right) {}
    Node(): sum(0), left(NULL), right(NULL) {}
};

int n;

Node* build(int l, int r, vector<int>& arr){
    if(l == r) return new Node(arr[l], NULL, NULL);
    int mid = (l+r)/2;
    Node* left = build(l, mid, arr);
    Node* right = build(mid+1, r, arr);
    return new Node(left->sum + right->sum, left, right);
}

Node* update(Node* prev, int l, int r, int pos, int val){
    if(l > pos || r < pos) return prev;
    if(l==r) return new Node(val, NULL, NULL);
    int mid = (l+r)/2;
    Node* left = update(prev->left, l, mid, pos, val);
    Node* right = update(prev->right, mid+1, r, pos, val);
    return new Node(left->sum + right->sum, left, right);
}

int query(Node* root, int l, int r, int ql, int qr){
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr) return root->sum;
    int mid = (l+r)/2;
    return query(root->left, l, mid, ql, qr) + query(root->right, mid+1, r, ql, qr);
}

int main(){
    int q;
    cin >> n >> q;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin >> arr[i];
    vector<Node*> version;
    version.push_back(build(0, n-1, arr));
    while(q--){
        int ver, l, r;
        cin >> ver >> l >> r; // 0-indexed
        cout << query(version[ver], 0, n-1, l, r-1) << "\n";
    }
    return 0;
}