Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja
Last active November 1, 2017 20:07
Show Gist options
  • Save kartikkukreja/431f6414f0f7b2dd84b3 to your computer and use it in GitHub Desktop.
Save kartikkukreja/431f6414f0f7b2dd84b3 to your computer and use it in GitHub Desktop.
Range Updates and Range Queries with BIT
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)
@vfolunin
Copy link

vfolunin commented Sep 6, 2014

I suppose there should be 'b' instead of 'j' in line 10.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment