Korotkodul

SECTION TREE. BEST VERSION

Dec 15th, 2021 (edited)
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.81 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. using namespace std;
  12. using ll = long long;
  13. using ld = long double;
  14. void cv(vector <ll> &v){
  15. for (auto x: v) cout<<x<<' ';
  16. cout<<"\n\n";
  17. }
  18. ld n;
  19. int N;
  20. vector <ll> a;
  21. int L,R;
  22.  
  23. int inter(int l, int r){
  24. //cout<<"LR= "<<L<<' '<<R<<'\n';
  25. //cout<<"lr= "<<l<<' '<<r<<'\n';
  26. if (l >= L && r <= R) {//cout<<"ONE\n";
  27. return 2;
  28. }
  29. else if (l < L && r >= L) {//cout<<"TWO\n";
  30. return 1;
  31. }
  32. else if (r > R && l <= R){//cout<<"THREE\n";
  33. return 1;
  34. }
  35. else return 0;
  36. }
  37. ll inf = pow(2, 63) - 100;
  38. struct tree{
  39. vector <ll> tot;//sum
  40. vector <ll> MIN;
  41. void bld(){
  42.  
  43. tot.assign(2*N-1,0);
  44. MIN.assign(2*N-1, inf);
  45. for (int i = 0; i < n; ++i){
  46. tot[N - 1 + i] = a[i];
  47. MIN[N - 1 + i] = a[i];
  48. }
  49. for (int i = N * 2 - 2; i >= 2; i-=2){
  50. int id = (i - 1) / 2;
  51. tot[id] = tot[i] + tot[i-1];
  52. MIN[id] = min(MIN[i], MIN[i-1]);
  53. }
  54. }
  55. void sh(){
  56. cv(tot);
  57. //cv(MIN);
  58. }
  59. ll getS(int l, int r, int id){
  60. //cout<<"id = "<<id<<"\n";
  61. int how = inter(l, r);
  62. //cout<<"how= "<<how<<'\n';
  63. if (how == 2) return tot[id];
  64. else if (how == 0) return 0;
  65. else{
  66. int m = (l + r) / 2;
  67. return getS(l, m, id*2+1) + getS(m+1, r, id*2+2);
  68. }
  69. }
  70. ll getMin(int l, int r, int id){
  71. int how = inter(l, r);
  72. if (how == 2) return MIN[id];
  73. else if (how == 0) return inf;
  74. else{
  75. int m = (l + r) / 2;
  76. return min(getMin(l, m, id*2+1) , getMin(m+1, r, id*2+2));
  77. }
  78. }
  79.  
  80. void chg(int id){
  81. tot[id] = tot[id*2 + 1] + tot[id*2 + 2];
  82. MIN[id] = min(tot[id*2 + 1], tot[id*2 + 2]);
  83. if (id == 0) return;
  84. chg( (id - 1) / 2);
  85. }
  86. };
  87.  
  88. tree wrk;
  89.  
  90. int main()
  91. {
  92. ios::sync_with_stdio(0);
  93. cin.tie(0);
  94. cout.tie(0);
  95. cin>>n;
  96. N = pow(2, ceil(log2(n)));
  97. a.assign(n, 0);
  98. wrk.bld();
  99. //wrk.sh();
  100. ll wht, x, y, res;
  101. while (true){
  102. cin>>wht;
  103. if (wht == 0) break;
  104. else if (wht == 1){
  105. cin>>x>>y;
  106.  
  107. x--;
  108. x += N - 1;
  109. //cout<<"start id= "<<x<<'\n';
  110. wrk.tot[x] += y;
  111. wrk.chg( (x-1) / 2);
  112. //wrk.sh();
  113. //cout<<"tot[0] = "<<wrk.tot[0]<<'\n';
  114. }else{
  115. cin>>L>>R;
  116. L--;
  117. R--;
  118. res = wrk.getS(0, N-1, 0);
  119. cout<<res<<'\n';
  120. }
  121. }
  122. }
  123. /*
  124. 2
  125. 1 1 4
  126. 2 1 1
  127. 2 1 1
  128. 0
  129.  
  130. 10
  131.  
  132. */
  133.  
Add Comment
Please, Sign In to add comment