Range Queries

class SegTree:
    def __init__(self, arr):
        n=len(arr); self.n=1
        while self.n<n: self.n<<=1
        self.t=[0]*(2*self.n)
        for i,v in enumerate(arr): self.t[self.n+i]=v
        for i in range(self.n-1,0,-1): self.t[i]=self.t[i<<1]+self.t[i<<1|1]
    def update(self, idx, val):
        i=self.n+idx; self.t[i]=val
        i>>=1
        while i: self.t[i]=self.t[i<<1]+self.t[i<<1|1]; i>>=1
    def query(self, l, r):
        l+=self.n; r+=self.n+1; res=0
        while l<r:
            if l&1: res+=self.t[l]; l+=1
            if r&1: r-=1; res+=self.t[r]
            l>>=1; r>>=1
        return res

class Fenwick:
    def __init__(self, n): self.n=n; self.bit=[0]*(n+1)
    def add(self, i, delta):
        i+=1
        while i<=self.n: self.bit[i]+=delta; i+=i&-i
    def sum(self, i):
        i+=1; s=0
        while i>0: s+=self.bit[i]; i-=i&-i
        return s
    def range_sum(self, l, r): return self.sum(r)-self.sum(l-1)

# Mo's algorithm skeleton
def mos_algorithm(arr, queries):
    import math
    n=len(arr); B=int(math.sqrt(n))
    queries=sorted(queries, key=lambda q: (q[0]//B, q[1] if (q[0]//B)%2==0 else -q[1]))
    curL=curR=0; curAns=0; ans=[0]*len(queries)
    def add(i):
        nonlocal curAns
        curAns += arr[i]
    def remove(i):
        nonlocal curAns
        curAns -= arr[i]
    for idx,(L,R) in enumerate(queries):
        while curL>L: curL-=1; add(curL)
        while curR<=R: add(curR); curR+=1
        while curL<L: remove(curL); curL+=1
        while curR>R+1: curR-=1; remove(curR)
        ans[idx]=curAns
    return ans