Dynamic Segment Tree - YessineJallouli/Competitive-Programming GitHub Wiki

#include <bits/stdc++.h>
#define ll long long
#define SaveTime ios_base::sync_with_stdio(false), cin.tie(0);
using namespace std;

const int N = 1e5+7;

struct node {
    long long sum;
    node *l;
    node *r;
    node() {
        sum = 0;
        l = NULL;
        r = NULL;
    }
    node(int _sum, node* _l, node* _r) {
        sum = _sum;
        l = _l;
        r = _r;
    }
};

node* insert(node* root, int pos, int val, int ns = -1e9, int ne = 1e9) {
    if (root == NULL) {
        root = new node();
    }
    if (pos < ns || pos > ne) {
        return root;
    }
    if (ns == ne) {
        root->sum = val;
        return root;
    }
    int md = (ns+ne)/2;
    node* n1 = insert(root->l, pos, val, ns, md);
    node* n2 = insert(root->r, pos, val, md+1, ne);
    if (root-> l == NULL && root->r == NULL) {
        root->sum = 0;
    }
    else if (root-> l == NULL) {
        root->sum = root->r->sum;
    }
    else if (root->r == NULL) {
        root->sum = root->l->sum;
    }
    else {
        root->sum = root->l->sum + root->r->sum;
    }
    return new node(root->sum, n1,n2);
}

int get(node* rst, int qs, int qe, int ns = -1e9, int ne = 1e9) {
    if (qs > ne || qe < ns)
        return 0;
    if (rst == NULL)
        return 0;
    if (ns >= qs && ne <= qe)
        return rst->sum;
    int md = (ns + ne) / 2;
    int n1 = get(rst->l, qs, qe, ns, md);
    int n2 = get(rst->r, qs, qe, md+1, ne);
    return n1+n2;
}

int main() {
    int n; cin >> n;
    node* dynTree = NULL;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        dynTree = insert(dynTree, i,x);
    }
}