"""Authored eight-value point-add/range-sum example, all ranges checked after updates."""
import json,platform
class Fenwick:
 def __init__(self,values):
  self.n=len(values);self.tree=[0]*(self.n+1)
  for i,x in enumerate(values):self.add(i,x)
 def add(self,index,delta):
  if type(index) is not int or not 0<=index<self.n:raise ValueError('external index0..n-1')
  return self._add_one_based(index+1,delta)
 def _add_one_based(self,i,delta):
  if type(i) is not int or not 1<=i<=self.n:raise ValueError('internal index1..n')
  path=[]
  while i<=self.n:self.tree[i]+=delta;path.append(i);i+=i&-i
  return path
 def prefix(self,end):
  if type(end) is not int or not 0<=end<=self.n:raise ValueError('prefix0..n')
  total=0;path=[];i=end
  while i>0:total+=self.tree[i];path.append(i);i-=i&-i
  return total,path
 def between(self,l,r):
  if not 0<=l<=r<=self.n:raise ValueError('half-open range')
  return self.prefix(r)[0]-self.prefix(l)[0]
def demo():
 values=[3,-1,4,2,0,5,-2,1];f=Fenwick(values);history=[];checks=0
 def verify():
  nonlocal checks
  for end in range(9):assert f.prefix(end)[0]==sum(values[:end]);checks+=1
  for l in range(9):
   for r in range(l,9):assert f.between(l,r)==sum(values[l:r]);checks+=1
 verify();initial=f.tree[:]
 for index,delta in [(0,2),(3,-3),(7,4),(2,-4)]:
  path=f.add(index,delta);values[index]+=delta;verify();history.append({'external_index':index,'delta':delta,'internal_update_path':path,'tree':f.tree[:],'values':values[:]})
 # A set operation is translated into delta using the independent current value.
 index,new=4,7;delta=new-values[index];path=f.add(index,delta);values[index]=new;verify();history.append({'set_index':index,'set_value':new,'translated_delta':delta,'internal_update_path':path,'tree':f.tree[:],'values':values[:]})
 coverage=[{'internal_index':i,'external_half_open':[i-(i&-i),i],'stored':f.tree[i]} for i in range(1,9)]
 for c in coverage:assert c['stored']==sum(values[slice(*c['external_half_open'])])
 rejects=[]
 for index in [-1,8,True]:
  try:f.add(index,1)
  except ValueError:rejects.append(repr(index))
  else:raise AssertionError('index invalid')
 try:f._add_one_based(0,1)
 except ValueError:internal_zero_rejected=True
 else:raise AssertionError('internal zero accepted')
 return {'runtime':platform.python_version(),'initial_values':[3,-1,4,2,0,5,-2,1],'initial_tree_one_based':initial,'history':history,'final_coverage':coverage,'final_prefix7':{'sum':f.prefix(7)[0],'internal_path':f.prefix(7)[1]},'prefix0':f.prefix(0)[0],'empty_range3_3':f.between(3,3),'all_prefix_range_assertions':checks,'rejected_indices':rejects,'internal_update_zero_rejected':internal_zero_rejected,'scope':'Integer point-add/prefix/half-open range sums, one-based internal tree; negative values allowed, no order-statistic search/concurrency/compression/benchmark guarantee.'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))