Блог пользователя pushkarmishra

What is the difference between a binary indexed tree and a segment tree?
Автор pushkarmishra, 12 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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")

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +7 Проголосовать: не нравится

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

            → Ответить