Hi everyone, Please help me finding out the mistake I did in Greg and Array. I am using Binary Indexed Tree to solve this problem and Implemented the idea of this site (main idea is given below, however, please visit the site for complete documentation of the algorithm)..
My complete code is Available In Pastebin
Algorithm that I tried to Implement:
update(ft, p, v):
for (; p <= N; p += p&(-p))
ft[p] += v
# Add v to A[a...b]
update(a, b, v):
update(B1, a, v)
update(B1, b + 1, -v)
update(B2, a, v * (a-1))
update(B2, b + 1, -v * b)
query(ft, b):
sum = 0
for(; b > 0; b -= b&(-b))
sum += ft[b]
return sum
# Return sum A[1...b]
query(b):
return query(B1, b) * b - query(B2, b)
# Return sum A[a...b]
query(a, b):
return query(b) - query(a-1)
Why are you even using BIT...? The problem is much easier than that.
I know it's a normal simulation problem. But I am trying to learn range update and range query of Binary Indexed Tree.
This problem can be done in O(m+n) you don't need BIT