SST

//keep in mind that the indexing is always 1-based inside of the structure so do the querying accordingly.
//If u spot some bug, then its in the way you query, because I have stress-tested the below version for any bugs.
#include<bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;

int log(int x) {
    return 32 - __builtin_clz(x) - 1;
}

int logll(ll x){
	return 64 - __builtin_clzll(x) - 1;
}

struct SST{
	int N, LOG, p = 1, jump = 1;
	vector<vector<ll>>S;
	SST(const vector<ll>&A){
		//Building the SST
		N = A.size() - 1;
		LOG = logll(N + 1) + 1;
		S.resize(N + 1);
		for(int i = 1 ; i <= N ; i++){
			S[i].resize(__builtin_ctz(i) + 1);
			S[i][0] = A[i];
		}
		while(jump <= N){
        jump <<= 1;
        for(int i = jump ; i <= N ; i += jump){
            S[i][p] = S[i][p - 1] + S[i - (jump >> 1)][p - 1];
        }
        p++;
 	   }
	}
	
	void update(int index, ll value){
		 int p = 1;
		 S[index][0] = value;
		 if(S[index].size() == 1){
		 	index += 1;
		 }
	    while(index <= N){
	 		 S[index][p] = S[index][p - 1] + S[index - (1 << (p - 1))][p - 1];
	 		 ++p;
	 		 if(p == S[index].size()){
	 			 index += (1ll << (p - 1));
	 		 }
		  }
	   }
	ll query(int L, int R){
		int answer = 0, d, p, i;
		while(R >= L && (R - (1ll << (S[R].size() - 1)) > L - 2)){
			answer += S[R].back();
			R -= (1ll << (S[R].size() - 1));
		}
		if(R < L){
			return answer;
		}
		d = R - L + 1;
		p = logll(d + 1);
		for(i = p ; i >= 0 ; i--){
			if((1ll << i)&d){
				answer += S[R][i];
				R -= (1ll << i);
			}
		}
		return answer;
	}
};