Please can anyone give examples of competetive programming problems which can be solved using Binary Indexed Trees but cannot be solved using Segment Trees ?
Please can anyone give examples of competetive programming problems which can be solved using Binary Indexed Trees but cannot be solved using Segment Trees ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
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.
explained clearly
http://www.quora.com/Data-Structures/How-does-one-decide-when-to-use-a-Segment-Tree-or-Fenwick-Tree
Easiest problems is around BIT 2D.
Segment tree 2D is pretty hard to code.