Skip to content

Instantly share code, notes, and snippets.

@kartikkukreja

kartikkukreja/Point Updates and Range Queries.py

Last active August 29, 2015 14:03
Show Gist options
  • Save kartikkukreja/6e5677a112f3d4111ea9 to your computer and use it in GitHub Desktop.
Save kartikkukreja/6e5677a112f3d4111ea9 to your computer and use it in GitHub Desktop.
Download ZIP
Point Updates and Range Queries with BIT
Raw
Point Updates and Range Queries.py
# Add v to A[p]
update(p, v):
for (; p <= N; p += p&(-p))
ft[p] += v
# Return sum A[1...b]
query(b):
sum = 0
for(; b > 0; b -= b&(-b))
sum += ft[b]
return sum
# Return sum A[a...b]
query(a, b):
return query(b) - query(a-1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment