fork download
copy 
  1.  
  2.  
  3. 				/* RANGE INCREMENT + RANGE SUM QUERIES + ITERATIVE */
  4.  
  5. using namespace std;
  6. #include <bits/stdc++.h>
  7.  
  8. struct SegLzy{
  9.     typedef long long ll;
  10.     #define _  j*2
  11.     #define __ j*2+1
  12.  
  13.     vector<ll> S,L; int n,h;
  14.  
  15.     SegLzy(vector<int> ar){
  16.         n=ar.size(); h=32-__builtin_clz(n);
  17.         S.assign(2*n,0); L.assign(n,0);
  18.         for(int i=0;i<n;i++)S[n+i]=ar[i];
  19.         for(int j=n-1;j>0;j--)S[j]=S[_]+S[__];  
  20.     }
  21.     inline void Push(int l,int r) {
  22.         ll s=h,k=1<<(h-1);
  23.         for(l+=n,r+=n-1;s>0;--s,k/=2){
  24.             for(int j=l>>s;j<=r>>s;++j)if(L[j]){
  25.                 S[_] +=L[j]*k;if(_ <n)L[_] +=L[j];
  26.                 S[__]+=L[j]*k;if(__<n)L[__]+=L[j];
  27.                 L[j] = 0;
  28.             }
  29.         }      
  30.     }
  31.     void Updt(int l,int r,int v){
  32.         ll s=l+n,e=r-1+n,k=1,j,c;
  33.         for(l+=n,r+=n;l<r;l/=2,r/=2,k*=2) {
  34.             if(l&1){S[l]+=v*k;if(l<n)L[l]+=v;l++;}
  35.             if(r&1){--r;S[r]+=v*k;if(r<n)L[r]+=v;}
  36.         }
  37.         j=s;c=1;while((j/=2)>0)c*=2,S[j]=S[_]+S[__]+L[j]*c;
  38.         j=e;c=1;while((j/=2)>0)c*=2,S[j]=S[_]+S[__]+L[j]*c;
  39.     }
  40.     long long Kqry(int l,int r,ll res=0){
  41.         Push(l,l+1);Push(r-1,r);
  42.         for(l+=n,r+=n;l<r;l/=2,r/=2){
  43.             if(l&1)res+=S[l++];
  44.             if(r&1)res+=S[--r];
  45.         }return res;
  46.     }
  47. };
  48.  
  49. int main(){
  50.     vector<int> a = {1,2,3,4,5,6,7,8,9,10};
  51.     SegLzy S1(a);
  52.     cout << S1.Kqry(0,10) << endl;
  53.     S1.Updt(3,7,10);
  54.     cout << S1.Kqry(3,7) << endl;
  55.     S1.Updt(3,7,-10);
  56.     cout << S1.Kqry(3,7) << endl;
  57. }
  58.  
  59. //------------------------------------------------------------------------
  60.  
  61. // struct SegLzy{
  62. //     typedef long long ll;
  63. //     vector<int> S,L; ll n,h;
  64.  
  65. //     SegLzy(vector<int> ar){
  66. //         n=ar.size(); h=32-__builtin_clz(n);
  67. //         S.assign(2*n,0); L.assign(n,0);
  68. //         for(int i=0;i<n;i++)S[n+i]=ar[i];
  69. //         for(int j=n-1;j>0;j--)S[j]=S[2*j]+S[2*j+1];  
  70. //     }
  71.  
  72. //     void calc(int p, int k) {
  73. //         S[p] = S[p<<1] + S[p<<1|1] + L[p] * k;
  74. //     }
  75.  
  76. //     void apply(int p, int value, int k) {
  77. //         S[p] += value * k;
  78. //         if (p < n) L[p] = value;
  79. //     }
  80.  
  81. //     void build(int l, int r) {
  82. //         int k = 2;
  83. //         for (l += n, r += n-1; l > 1; k <<= 1) {
  84. //             l >>= 1, r >>= 1;
  85. //             for (int i = r; i >= l; --i) calc(i, k);
  86. //         }
  87. //     }
  88.  
  89. //     void push(int l, int r) {
  90. //         int s = h, k = 1 << (h-1);
  91. //         for (l += n, r += n-1; s > 0; --s, k >>= 1)
  92. //             for (int i = l >> s; i <= r >> s; ++i) if (L[i] != 0) {
  93. //                 apply(i<<1, L[i], k);
  94. //                 apply(i<<1|1, L[i], k);
  95. //                 L[i] = 0;
  96. //             }
  97. //     }
  98.  
  99. //     void modify(int l, int r, int value) {
  100. //         if (value == 0) return;
  101. //         push(l, l + 1);
  102. //         push(r - 1, r);
  103. //         int l0 = l, r0 = r, k = 1;
  104. //         for (l += n, r += n; l < r; l >>= 1, r >>= 1, k <<= 1) {
  105. //             if (l&1) apply(l++, value, k);
  106. //             if (r&1) apply(--r, value, k);
  107. //         }
  108. //         build(l0, l0 + 1);
  109. //         build(r0 - 1, r0);
  110. //     }
  111.  
  112. //     int query(int l, int r) {
  113. //         push(l, l + 1);
  114. //         push(r - 1, r);
  115. //         int res = 0;
  116. //         for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  117. //             if (l&1) res += S[l++];
  118. //             if (r&1) res += S[--r];
  119. //         }
  120. //         return res;
  121. //     }
  122. // };
  123.  
  124. // int main(){
  125. //     vector<int> a = {1,2,3,4,5,6,7,8,9,10};
  126. //     SegLzy S1(a);
  127. //     cout << S1.query(0,10) << endl;
  128. //     S1.modify(3,7,10);
  129. //     cout << S1.query(3,7) << endl;
  130. //     S1.modify(3,7,-10);
  131. //     cout << S1.query(3,7) << endl;
  132. // }
  133.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
55
62
22
https://ideone.com/s6mTgd
RANGE INCREMENT + RANGE SUM QUERIES + ITERATIVE
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!