StoneCold_'s blog

Segment Tree and BIT
By StoneCold_, 10 years ago, In English

Please can anyone give examples of competetive programming problems which can be solved using Binary Indexed Trees but cannot be solved using Segment Trees ?

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

every problem solvable using Binary Indexed Tree is also solvable using Segment Tree (but the converse is not true).
however, the code for BIT is much much shorter than that for ST (for most problems), so i would advise BIT for such type of problems.

→ Reply
»
10 years ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

explained clearly

http://www.quora.com/Data-Structures/How-does-one-decide-when-to-use-a-Segment-Tree-or-Fenwick-Tree

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Easiest problems is around BIT 2D.

  • IOI 2001 — Mobile

Segment tree 2D is pretty hard to code.

→ Reply