@rsj1308 - In this question , suppose we want to update range [2 4] with value 1, thus first we call update(2) which will update node 2,node 4 and node 8(lets say length of bit array is 10) with value 1. Now call update (5) and this will update node 5, node 6 and node 8 but with -1. Now doing a point query will back trace all the node and the nodes which were not within the range get updated with negative number and that within the range gets updated with positive number. Once you back trace these will cancel out and gives you the correct result.
Its absolutely non-sense that this question can’t get AC without fast input output. Even with printf scanf and correct efficient algo it gets TLE’d and with fast input it gets AC.
What is the reason behind “query(x) doesn’t return the sum of the elements having key less then or equal to x and update segment(u,v) with val = k is same as update(u,k),update(v+1,-k)”?
Segment trees are usually meant for range queries, but here we are just interested in getting the value of one element.
update(u,k): add k to values for 1 to u
update(v,k): add k to values for 1 to v
So, to add k to range (u,v), you have to do update(u,k); update(v+1,-k).
import sys
inp=sys.stdin.readline
n,m,c=map(int,inp().split())
ft=[0]*(n+1)
def update(i,val):
while i<=n:
ft[i]+=val
i += i & -i
def query(i):
ans=0
while i>0:
ans+=ft[i]
i -= i & -i
return ans
update(1,c)
for _ in range(m):
arr=list(inp().split())
if arr[0]=="Q":
p=int(arr[1])
res=query(p)
print(res)
else:
u,v,k=int(arr[1]),int(arr[2]),int(arr[3])
update(u,k)
update(v+1,-k)