summ

summ_node.cpp

#include <iostream>

using namespace std;

#include <cstdlib>
#include <algorithm>
#include <vector>

struct node {
    int left, right, val;
    node *child_left, *child_right;

};

node *build(int left, int right, vector<int> &a) {
    node *res = new node;
    res->left = left;
    res->right = right;

    if (left == right) {
        res->child_left = res->child_right = 0;
        res->val = a[left];
    } else {
        int mid = (left + right) / 2;
        res->child_left = build(left, mid, a);
        res->child_right = build(mid + 1, right, a);
        res->val = 0;


    }
    return res;

};


int query(node *root, int i) {
    if (i < root->left || i > root->right) {
        return 0;
    }
    if (root->left == root->right) {
        return root->val;

    }
    int ans1 = query(root->child_left, i);
    int ans2 = query(root->child_right, i);
    return ans1 + ans2 + root->val;


}


void update(node *root, int left, int right, int delta) {

    if (right < root->left || left > root->right) {
        return;

    }
    if (left <= root->left && root->right <= right) {
        root->val += delta;
        return;
    }

    update(root->child_left, left,right,delta);
    update(root->child_right, left,right,delta);



}

int main() {
    const int n = 100;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = i % 10;
    }
    node *root = build(1, n, a);
    cout<<query(root,35)<<endl;
    update(root,10,90,1);
    cout<<query(root,35)<<endl;
    update(root,35,100,1);
    cout<<query(root,35)<<endl;

}