Segment Tree Range Sum
Programming Interview
Hard
5 views
Problem Description
Given {x}, Two types: 1 i x means set a[i]=x, 2 l r means output sum of a[l..r] (1-based). Implement build/update/query helpers.
Input Format
First line n q. Second line n integers. Next q lines queries.
Output Format
For type 2 print sums.
Sample Test Case
Input:
5 5
1 2 3 4 5
2 1 3
1 2 10
2 2 5
1 5 -1
2 1 5
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); q=int(next(it))
a=[0]+[int(next(it)) for _ in range(n)]
size=1
while size<n:
size*=2
seg=[0]*(2*size)
def build():
for i in range(n):
seg[size+i]=a[i+1]
for i in range(size-1,0,-1):
seg[i]=seg[2*i]+seg[2*i+1]
def update(idx,val):
pos=size+(idx-1)
seg[pos]=val
pos//=2
while pos:
seg[pos]=seg[2*pos]+seg[2*pos+1]
pos//=2
def query(l,r):
l=size+(l-1)
r=size+(r-1)
s=0
while l<=r:
if (l%2)==1:
s+=seg[l]
l+=1
if (r%2)==0:
s+=seg[r]
r-=1
l//=2
r//=2
return s
build()
out=[]
for _ in range(q):
t=int(next(it))
if t==1:
i=int(next(it)); x=int(next(it))
update(i,x)
else:
l=int(next(it)); r=int(next(it))
out.append(str(query(l,r)))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!