4

I don't have a scenario. But for the generic case where we have to just

  1. Update in a range (example clear all values in some range i-j)
  2. Query for some value in a range. (example RMQ)
  3. Make an update on an individual element ( a specific case of point 1)
  4. Search for a particular value in a range ( again a specific case of point 2)

All these operations can be performed with either a BIT or a segment tree.But except 3 and some specific cases of 2 segment tree is much more efficient. (Infact BIT doesn't helps in any way for queries like RMQ)

The most clear advantage of BIT is its far easier to code.

4

1 回答 1

0

(Here are my thoughts after spending time with segment tree and BIT problems since few weeks, so i am quite new it)

BIT is easier to code, but there are situations which you can easily visualize and relate to a segment tree. Another advantage that BIT offers is that it takes the lesser space (O(n) space).

From what i feel, segment trees are easier to understand compared to BIT, so you can easily apply and relate it to a given situation. Lazy propagation is also simpler and easy to understand in segment trees. Thus, Segment tree lets you efficiently update over a range.

于 2012-08-04T14:44:05.787 回答