t3rminated's blog

update in BIT
By t3rminated, history, 8 years ago, In English

If i have an update condition like if i want to assign all elements in range (l,r) with a value x(x!=0) and i have many updates like this , for example —

l r x

1 4 2

3 4 3

7 8 9

now if i want to query for an index y , then can i do this using BIT? I have come up with this solution but it isn't working —

update(l, x)

update(r+1, 0) #0 means index still unassigned.

now if i query for like index 4(read(4) — read(4-1)) i am not getting the correct answer. Is my approach correct ?

Tags bit
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

why not segment tree?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

AFAIK there is no way to perform range assignment for BIT, but in case if you are talking about range addition (you are performing a[i] += x instead of a[i] = x for the range [l, r]), reversing the update and query function could do the job.

Example

Your method does not work for assignment... I mean, why should it work? Literally it means a[l] += x for an trivial BIT.

If you are talking about range assignment, as qingczha has already mentioned, learn segment tree and lazy propagation.

→ Reply