/*
*   author: kartik8800
*/
 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a,b) for(int i = a; i < b; i++)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL<<60)`
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define goog(tno) cout << "Case #" << tno++ <<": "
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define read(x) int x; cin >> x
using namespace std;

void init_code(){
    fast_io;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif 
}

struct Chunk{
    std::vector<int> elementsInChunk;
    int aggregatedValueForChunk;
};

class SquareRootDecomposition{
    int block_size;
    vector<Chunk> chunks;
    
    // returns {chunk_number, index_inside_chunk} for given index.
    pair<int,int> getChunkForIndex(int index){
        int chunk_number = index / block_size;
        int index_inside_chunk = index - (chunk_number * block_size);
        return {chunk_number, index_inside_chunk};
    }

    int calculateAggregatedValue(Chunk& chunk, int index_from, int index_till){
        int aggregatedValue = 0;
        while(index_from <= index_till)
            aggregatedValue += chunk.elementsInChunk[index_from++];
        return aggregatedValue;
    }

    void fillChunks(vector<int>& dataVector){
        int curr_chunk = 0;
        for(int i = 0; i < dataVector.size(); i++){
            if(i != 0 && ((i % block_size) == 0)){
                curr_chunk++;
            }
            chunks[curr_chunk].elementsInChunk.push_back(dataVector[i]);
        }

        for(Chunk &chunk: chunks){
            chunk.aggregatedValueForChunk = calculateAggregatedValue(
                  chunk, 0, (int)chunk.elementsInChunk.size() - 1);
        }
    }

    int internalChunks(int l, int r){
        if(l > r) return 0;
        int aggregatedValue = 0;
        while(l <= r)
            aggregatedValue += chunks[l++].aggregatedValueForChunk;
        return aggregatedValue;
    }

public:
    SquareRootDecomposition(std::vector<int>& dataVector){
        block_size = sqrt((int)dataVector.size());       
        chunks = vector<Chunk>(block_size + 1);
        fillChunks(dataVector);          
    }

    int query(int L, int R){
        pair<int,int> leftChunk = getChunkForIndex(L);
        pair<int,int> rightChunk = getChunkForIndex(R);
        if(leftChunk.first == rightChunk.first)
            return calculateAggregatedValue(chunks[leftChunk.first], leftChunk.second, rightChunk.second);
        else {
           return calculateAggregatedValue(chunks[leftChunk.first], leftChunk.second, (int)chunks[leftChunk.first].elementsInChunk.size() - 1) 
                      + calculateAggregatedValue(chunks[rightChunk.first], 0, rightChunk.second)
                      + internalChunks(leftChunk.first + 1, rightChunk.first - 1);
        }
    }

    void update(int index, int value){
        pair<int,int> indexInChunk = getChunkForIndex(index);
        chunks[indexInChunk.first].elementsInChunk[indexInChunk.second] = value;
        chunks[indexInChunk.first].aggregatedValueForChunk = calculateAggregatedValue(chunks[indexInChunk.first], 0, chunks[indexInChunk.first].elementsInChunk.size());
    }
};

int main() {
   init_code();
   int t = 1; //cin >> t; 
   while(t--){
      std::vector<int> v = {1,2,3,4,5,6,7,8,9,10};
      SquareRootDecomposition myQueryHelper(v);
      cout << myQueryHelper.query(0, 5) << '\n';; // should print 1+2+3+4+5+6
      myQueryHelper.update(2,0);
      cout << myQueryHelper.query(0, 5) << '\n'; // should print 1+2+0+4+5+6
   }
   return 0;
}