fork download
copy 
  1. /*
  2. *   author: kartik8800
  3. */
  4.  
  5. #include<bits/stdc++.h>
  6. #define ll long long
  7. #define pb push_back
  8. #define fr(a,b) for(int i = a; i < b; i++)
  9. #define rep(i,a,b) for(int i = a; i < b; i++)
  10. #define mod 1000000007
  11. #define inf (1LL<<60)`
  12. #define all(x) (x).begin(), (x).end()
  13. #define prDouble(x) cout << fixed << setprecision(10) << x
  14. #define triplet pair<ll,pair<ll,ll>>
  15. #define goog(tno) cout << "Case #" << tno++ <<": "
  16. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  17. #define read(x) int x; cin >> x
  18. using namespace std;
  19.  
  20. void init_code(){
  21.     fast_io;
  22.     #ifndef ONLINE_JUDGE
  23.     freopen("input.txt", "r", stdin);
  24.     freopen("output.txt", "w", stdout);
  25.     #endif 
  26. }
  27.  
  28. struct Chunk{
  29.     std::vector<int> elementsInChunk;
  30.     int aggregatedValueForChunk;
  31. };
  32.  
  33. class SquareRootDecomposition{
  34.     int block_size;
  35.     vector<Chunk> chunks;
  36.  
  37.     // returns {chunk_number, index_inside_chunk} for given index.
  38.     pair<int,int> getChunkForIndex(int index){
  39.         int chunk_number = index / block_size;
  40.         int index_inside_chunk = index - (chunk_number * block_size);
  41.         return {chunk_number, index_inside_chunk};
  42.     }
  43.  
  44.     int calculateAggregatedValue(Chunk& chunk, int index_from, int index_till){
  45.         int aggregatedValue = 0;
  46.         while(index_from <= index_till)
  47.             aggregatedValue += chunk.elementsInChunk[index_from++];
  48.         return aggregatedValue;
  49.     }
  50.  
  51.     void fillChunks(vector<int>& dataVector){
  52.         int curr_chunk = 0;
  53.         for(int i = 0; i < dataVector.size(); i++){
  54.             if(i != 0 && ((i % block_size) == 0)){
  55.                 curr_chunk++;
  56.             }
  57.             chunks[curr_chunk].elementsInChunk.push_back(dataVector[i]);
  58.         }
  59.  
  60.         for(Chunk &chunk: chunks){
  61.             chunk.aggregatedValueForChunk = calculateAggregatedValue(
  62.                   chunk, 0, (int)chunk.elementsInChunk.size() - 1);
  63.         }
  64.     }
  65.  
  66.     int internalChunks(int l, int r){
  67.         if(l > r) return 0;
  68.         int aggregatedValue = 0;
  69.         while(l <= r)
  70.             aggregatedValue += chunks[l++].aggregatedValueForChunk;
  71.         return aggregatedValue;
  72.     }
  73.  
  74. public:
  75.     SquareRootDecomposition(std::vector<int>& dataVector){
  76.         block_size = sqrt((int)dataVector.size());       
  77.         chunks = vector<Chunk>(block_size + 1);
  78.         fillChunks(dataVector);          
  79.     }
  80.  
  81.     int query(int L, int R){
  82.         pair<int,int> leftChunk = getChunkForIndex(L);
  83.         pair<int,int> rightChunk = getChunkForIndex(R);
  84.         if(leftChunk.first == rightChunk.first)
  85.             return calculateAggregatedValue(chunks[leftChunk.first], leftChunk.second, rightChunk.second);
  86.         else {
  87.            return calculateAggregatedValue(chunks[leftChunk.first], leftChunk.second, (int)chunks[leftChunk.first].elementsInChunk.size() - 1) 
  88.                       + calculateAggregatedValue(chunks[rightChunk.first], 0, rightChunk.second)
  89.                       + internalChunks(leftChunk.first + 1, rightChunk.first - 1);
  90.         }
  91.     }
  92.  
  93.     void update(int index, int value){
  94.         pair<int,int> indexInChunk = getChunkForIndex(index);
  95.         chunks[indexInChunk.first].elementsInChunk[indexInChunk.second] = value;
  96.         chunks[indexInChunk.first].aggregatedValueForChunk = calculateAggregatedValue(chunks[indexInChunk.first], 0, chunks[indexInChunk.first].elementsInChunk.size());
  97.     }
  98. };
  99.  
  100. int main() {
  101.    init_code();
  102.    int t = 1; //cin >> t; 
  103.    while(t--){
  104.       std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
  105.       SquareRootDecomposition myQueryHelper(v);
  106.       cout << myQueryHelper.query(0, 5) << '\n';; // should print 1+2+3+4+5+6
  107.       myQueryHelper.update(2,0);
  108.       cout << myQueryHelper.query(0, 5) << '\n'; // should print 1+2+0+4+5+6
  109.    }
  110.    return 0;
  111. }
Success #stdin #stdout 0.01s 5356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
21
18
https://ideone.com/eg4y3S
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

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!