arrch's blog

Help with Binary Indexed Tree
By arrch, history, 9 years ago, In English

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.

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

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

You should read about Segment Tree. This blog relly helped me to understand it — segment tree!

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

there are great tutorial on russian: tutorial, you can translate it with any translator.

→ Reply
»
9 years ago, # |
← Rev. 6   Vote: I like it +19 Vote: I do not like it

There is a variant of BIT Trees that does range_update & point_query we will use this one

To update a range [l, r] with value V (incrementing every element in range by V), we add V to

Unable to parse markup [type=CF_TEX]

and subtract it from

Unable to parse markup [type=CF_TEX]

, since bit tree returns for

Unable to parse markup [type=CF_TEX]

we always get the right results for point queries

Now in order to make range_queries and range_updates, lets have a look at our array a:

Unable to parse markup [type=CF_TEX]

Calling

Unable to parse markup [type=CF_TEX]

should make it like this:

Unable to parse markup [type=CF_TEX]

And prefix_sum array:

Unable to parse markup [type=CF_TEX]

Let's divide the array into 3 parts:

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

should return 0

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

should return

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

should return

Unable to parse markup [type=CF_TEX]

So basically,

Unable to parse markup [type=CF_TEX]

is now like a linear function of index x:

Unable to parse markup [type=CF_TEX]

The terms that depend on x can be stored in a bit tree and other terms in another bit tree

Pseudo_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)
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, now it's clear for me, thank you ^^

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      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

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

        Thanks, sorry for forgetting such important thing :D

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

          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.

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

            Yes! That should have been minus instead of plus.

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

Read this Blog : Various Usage Of BIT

→ Reply