Sqrt decomposition

// Bhupendra Yadav
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int blk_size, sqr[N], arr[N * N];

void upd(int index, int val){
    int i = index / blk_size + (index % blk_size != 0);
    sqr[i] += val - arr[index];
    arr[index] = val;
}

int ans(int l, int r){
  int x = l / blk_size;
  if(l % blk_size)x++;
  x *= blk_size;
    int32_t sum = 0;
   // cout << x << ' ' ;


    while(l <= min(x,r))sum += arr[l++];
    if(l > r)return sum;
    x /= blk_size;
    x++;
    int y = r / blk_size;
   // cout << "sum = " << sum << ' ' ;
    if(r % blk_size == 0)y--;
   // cout << x << ' ' << y << endl;
   while(x <= y)sum += sqr[x],x++;

   y = y * blk_size + 1;
   while(y <= r)sum += arr[y], y++;

   return sum;

}

int main(){
    int n, m, i;long int sum = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
      cin >> arr[i];
    blk_size = sqrt(n);
    if(blk_size * blk_size != n)blk_size ++;

    cout << blk_size << endl;
    // precompute
    for(i = 1; i <= n; i++){
      sum += arr[i];
      if(i % blk_size == 0)
        sqr[i / blk_size] = sum,sum = 0;;

    }
    for(int i = 0; i < m; i++){
            int c, l , r;
      cin >> c;
      if(c == 1){
      cin >> l >> r;
      cout << ans(l, r) << endl;
      }
      else {
        int index, val;
        cin >> index >> val;
        upd(index, val);
      }
    }











}