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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 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 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 153 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.06.2024 15:39:59 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
A Binary Indexed Tree (BIT) is used to store cumulative sums. You have an array
Unable to parse markup [type=CF_TEX]
. 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
Unable to parse markup [type=CF_TEX]
. 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.
Thank you so much. By the way, what is range updating point querying in BIT? How does it work?
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
Unable to parse markup [type=CF_TEX]
andUnable to parse markup [type=CF_TEX]
, thus usingUnable to parse markup [type=CF_TEX]
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 ifUnable to parse markup [type=CF_TEX]
); then you call a second time the update function on theUnable to parse markup [type=CF_TEX]
-th element (because from theUnable to parse markup [type=CF_TEX]
-th element on, the change must not affect anymore), this time you want to undo the update you have done, so you update byUnable to parse markup [type=CF_TEX]
.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")
Thank you so much. And any good books where I can read about them extensively?
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.
Thanx for this man! It's great help. Currently trying to learn both of them. This has been a lot of help. :)