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

Segment Tree and BIT
Автор StoneCold_, 10 лет назад, По-английски

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

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

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

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.

→ Ответить
»
10 лет назад, # |
← Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

explained clearly

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

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Easiest problems is around BIT 2D.

  • IOI 2001 — Mobile

Segment tree 2D is pretty hard to code.

→ Ответить