pushkarmishra's blog

What is the difference between a binary indexed tree and a segment tree?
By pushkarmishra, 12 years ago, In English

I have just started to learn these advanced data structures. I can't make out where to use which one. Also, if you could suggest some good books where I can find the topic of segment trees. Thank you.

  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
12 years ago, # |
  Vote: I like it +28 Vote: I do not like it

A Binary Indexed Tree (BIT) is used to store cumulative sums. You have an array a0, a1, ..., an. You want to be able to retrieve the sum of the first k elements in O(logn) time, and you want to be able to add a quantity q to the i-th element in O(logn) time. Note that these two operations can be implemented with a normal array, but the time complexity will be O(n) and O(1). Tutorial here.

A segment tree (sometimes called range tree) is a much more flexible data structure, you can use it to store many different things. You have an array a0, a1, ..., an. You want to be able to retrieve the sum (or the maximum, or the minimum, or the greatest common divisor, or another associative function) of the elements between the l-th and the r-th in O(logn) time, and you want to be able to add (or to overwrite, or to multiply by...) a quantity q to the i-th element (or to every element between the l-th and the r-th) in O(logn) time. Tutorial here and here.

Segment trees (as well as BITs) can be generalized to k dimensions. Often a problem will require you to implement a 2d segment tree (or BIT).

It is possible to simulate a BIT using a segment tree, so you might ask: why would you prefer a BIT over a segment tree? Well, a BIT is much easier to code and requires less memory. So if a BIT is enough to solve the problem, go for it, else try with a segment tree.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank you so much. By the way, what is range updating point querying in BIT? How does it work?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Do you mean range updating (add a quantity q to every element between the l-th and the r-th) and point querying (query the value of the i-th element) using a BIT?

      It is possible, there is a nice "trick" to do that. If you're asked to add q to every element between the l-th and the r-th, you will only call update(l,  + q) and update(r + 1,  - q), thus using 2 × O(logn) time. If you're asked the value of the i-th element, then you will return the sum of the first i values instead (you already know how to do that in O(logn) time). This trick works perfectly: when you update the value of the l-th element, every element between the l-th and the last will be affected by this change (that's because when you ask for the sum of the first k elements, the result will be different only if k ≥ l); then you call a second time the update function on the (r + 1)-th element (because from the (r + 1)-th element on, the change must not affect anymore), this time you want to undo the update you have done, so you update by  - q.

      I recently used this trick in this submission: 3185302. Another problem (a little more difficult) where you can use this trick is this: COCI CONTEST #3 (search for the task named "PLACE")

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thank you so much. And any good books where I can read about them extensively?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I don't know any book which talks about BITs or Segment trees, I learned it by reading tutorials. An awesome website for algorithm tutorials is e-maxx.ru/algo though it's in russian. I studied segment trees there (and many other nice things, like the Z-algorithm) using google translate.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            Thanx for this man! It's great help. Currently trying to learn both of them. This has been a lot of help. :)

            → Reply