### arrch's blog

By arrch, history, 4 years ago,

Hello cf! I am solving this problem http://www.spoj.com/problems/HORRIBLE/ . And I don't know how to implement BIT with range modification. Please help me. Thanks.

• 0

 » 4 years ago, # | ← Rev. 2 →   +5 You should read about Segment Tree. This blog relly helped me to understand it — segment tree!
•  » » 4 years ago, # ^ |   0 I know about segment tree. But now I am learning BIT, so I want to solve this problem using this data structure :)
 » 4 years ago, # |   0 there are great tutorial on russian: tutorial, you can translate it with any translator.
•  » » 4 years ago, # ^ |   0 It's ok, I know Russian. Thanks a lot. :)
 » 4 years ago, # | ← Rev. 6 →   +19 There is a variant of BIT Trees that does range_update & point_query we will use this oneTo update a range [l, r] with value V (incrementing every element in range by V), we add V to bit[l] and subtract it from bit[r + 1], since bit tree returns for we always get the right results for point queriesNow in order to make range_queries and range_updates, lets have a look at our array a:[0, 0, 0, 0, 0, 0]Calling update(l = 3, r = 5, v = 5) should make it like this:[0, 0, 5, 5, 5, 0]And prefix_sum array: [0, 0, 5, 10, 15, 15]Let's divide the array into 3 parts:a[1, ..., l - 1] query(x) should return 0a[l, ..., r] query(x) should return V × (x - (l - 1)) = Vx - V(l - 1)a[r + 1, ..., N] query(x) should return V × (r - (l - 1)) = Vr - V(l - 1)So basically, query(x) is now like a linear function of index x: f(x) = Ax + BThe terms that depend on x can be stored in a bit tree and other terms in another bit treePseudo_code: update_point(bit, x, v): while(x <= N): bit[x] += v x += x&-x update_range(l, r, v): update_point(bitAX, l, v) update_point(bitAX, r+1, -v) update_point(bitB, l, -v * (l-1)) update_point(bitB, r+1, v * r) query_point(bit, x) sum = 0 while(x > 0): sum += bit[x] x += x&-x query(x): return x * query_point(bitAX, x) + query_point(bitB, x) query(l, r): return query(r) + query(l-1) 
•  » » 4 years ago, # ^ |   0 Wow, now it's clear for me, thank you ^^
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +1 But in function update_range(..) in second row u should write update_point(bitAX, r+1, -v)You are forgot a minus before "v" :)UPD: fixed
•  » » » » 4 years ago, # ^ |   0 Thanks, sorry for forgetting such important thing :D
•  » » » » » 4 years ago, # ^ |   0 Thank you for your perfect explanation! Is not query (r) -query (l-1) on the last line? I think it should be minus, not plus.
•  » » » » » » 4 years ago, # ^ |   0 Yes! That should have been minus instead of plus.
 » 4 years ago, # |   0 Read this Blog : Various Usage Of BIT
•  » » 4 years ago, # ^ |   0 Thanks, it's very useful