Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <tuple>
- #include <algorithm>
- #include <utility>
- using namespace std;
- #define ll long long int
- struct node {
- ll left, right, val;
- node* child_left, * child_right;
- };
- node* build(const vector<ll>& a, ll left, ll right)
- {
- node* root = new node;
- root->left = left;
- root->right = right;
- if (left == right)
- {
- root->val = a[left];
- root->child_left = root->child_right = nullptr;
- }
- else
- {
- int middle = (left + right) / 2;
- root->child_left = build(a, left, middle);
- root->child_right = build(a, middle + 1, right);
- root->val = 0;
- }
- return root;
- }
- int query(node* root, int i)
- {
- if (i < root->left || i > root->right)
- return 0;
- if (root->left == root->right)
- return root->val;
- return
- query(root->child_left, i)
- +
- query(root->child_right, i)
- +
- root->val;
- ;
- }
- void update(node* root, ll l, ll r, ll delta)
- {
- if (r < root->left || l > root->right)
- return;
- if (l <= root->left && r >= root->right)
- {
- root->val += delta;
- return;
- }
- update(root->child_left, l, r, delta);
- update(root->child_right, l, r, delta);
- }
- int main()
- {
- ll n, m;
- ll x, y, delta;
- char ch;
- vector<ll> a, answ;
- cin >> n;
- a.push_back(0);
- for (ll i = 0; i < n; ++i)
- {
- cin >> x;
- a.push_back(x);
- }
- node* root = build(a, 1, n);
- cin >> m;
- for (ll i = 0; i < m; ++i)
- {
- cin >> ch;
- if (ch == 'g')
- {
- cin >> x;
- cout << query(root, x) << endl;
- }
- if (ch == 'a')
- {
- cin >> x >> y >> delta;
- update(root, x, y, delta);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement