Advertisement
OMEGAHEAD_MonkoX

Untitled

Oct 18th, 2020
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <tuple>
  4. #include <algorithm>
  5. #include <utility>
  6.  
  7. using namespace std;
  8.  
  9. #define ll long long int
  10.  
  11.  
  12.  
  13.  
  14.  
  15. struct node {
  16. ll left, right, val;
  17. node* child_left, * child_right;
  18. };
  19.  
  20. node* build(const vector<ll>& a, ll left, ll right)
  21. {
  22. node* root = new node;
  23. root->left = left;
  24. root->right = right;
  25. if (left == right)
  26. {
  27. root->val = a[left];
  28. root->child_left = root->child_right = nullptr;
  29. }
  30. else
  31. {
  32. int middle = (left + right) / 2;
  33. root->child_left = build(a, left, middle);
  34. root->child_right = build(a, middle + 1, right);
  35. root->val = 0;
  36. }
  37. return root;
  38. }
  39.  
  40. int query(node* root, int i)
  41. {
  42. if (i < root->left || i > root->right)
  43. return 0;
  44. if (root->left == root->right)
  45. return root->val;
  46. return
  47. query(root->child_left, i)
  48. +
  49. query(root->child_right, i)
  50. +
  51. root->val;
  52. ;
  53. }
  54.  
  55. void update(node* root, ll l, ll r, ll delta)
  56. {
  57. if (r < root->left || l > root->right)
  58. return;
  59. if (l <= root->left && r >= root->right)
  60. {
  61. root->val += delta;
  62. return;
  63. }
  64. update(root->child_left, l, r, delta);
  65. update(root->child_right, l, r, delta);
  66. }
  67.  
  68.  
  69.  
  70. int main()
  71. {
  72. ll n, m;
  73. ll x, y, delta;
  74. char ch;
  75. vector<ll> a, answ;
  76. cin >> n;
  77. a.push_back(0);
  78. for (ll i = 0; i < n; ++i)
  79. {
  80. cin >> x;
  81. a.push_back(x);
  82. }
  83.  
  84. node* root = build(a, 1, n);
  85. cin >> m;
  86. for (ll i = 0; i < m; ++i)
  87. {
  88. cin >> ch;
  89. if (ch == 'g')
  90. {
  91. cin >> x;
  92. cout << query(root, x) << endl;
  93. }
  94. if (ch == 'a')
  95. {
  96. cin >> x >> y >> delta;
  97. update(root, x, y, delta);
  98. }
  99. }
  100.  
  101.  
  102. return 0;
  103.  
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement