Advertisement
Guest User

xd

a guest
Aug 21st, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. template<typename T>
  6. struct tree {
  7. int n = 1;
  8. int s;
  9. vector<T> elements;
  10. tree(int _n){
  11. while (n < _n){
  12. n *= 2;
  13. }
  14. n*=2;
  15. elements.resize(n);
  16. n /= 2;
  17. }
  18. void add(int a, int b, int l, int r, int i, T toadd){
  19. if (a <= l and r <= b){
  20. elements[i] += toadd;
  21. return;
  22. }
  23. int mid = (l+r)/2;
  24. if (a <= mid) add(a, b, l, mid, 2*i, toadd);
  25. if (mid + 1 <= b) add(a, b, mid + 1, r, 2*i+1, toadd);
  26. return;
  27. }
  28. T read(int i){
  29. i += n;
  30. T result = 0;
  31. while (i != 0){
  32. result += elements[i];
  33. i/=2;
  34. }
  35. return result;
  36. }
  37. void print(){
  38. int i = 1;
  39. int m = 1;
  40. int lim = n*2;
  41. while (i < lim){
  42. while (i < m){
  43. cout << elements[i] << ' ';
  44. i++;
  45. }
  46. m *= 2;
  47. cout << "\n";
  48. }
  49. }
  50. };
  51.  
  52. int main(){
  53. ios_base::sync_with_stdio(0);
  54. cin.tie(0);
  55. cout.tie(0);
  56. int n, m;
  57. cin >> n >> m;
  58. tree<ll> T(n);
  59. while (m-->0){
  60. char q;
  61. cin >> q;
  62. if (q == '+'){
  63. int a, b, x;
  64. cin >> a >> b >> x;
  65. T.add(a-1, b-1, 0, T.n-1, 1, x);
  66. }
  67. if (q == '?'){
  68. int i;
  69. cin >> i;
  70. cout << T.read(i-1) << '\n';
  71. }
  72. }
  73. // T.print();
  74. return 0;
  75. }
  76. /*
  77. 10 5
  78. + 1 5 2
  79. ? 4
  80. + 2 8 99
  81. ? 3
  82. ? 9
  83. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement