Как эффективно обрабатывать запросы вида "Найти сумму элементов, таких что x < a[i] < y на отрезке l < i < r" с изменением в элементе с помощью дерева отрезков?
Как эффективно обрабатывать запросы вида "Найти сумму элементов, таких что x < a[i] < y на отрезке l < i < r" с изменением в элементе с помощью дерева отрезков?
№ | Пользователь | Рейтинг |
---|---|---|
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 | 173 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | pajenegod | 145 |
Название |
---|
ну когда ты строишь дерево отрезков , в функции build там где l==r проверяй если число соответствует твоему условию то t[v]=a[l]; а если нет то t[v]=0;
3d Mo
Пусть для каждой вершины дерева отрезков мы храним весь ее подотрезок в двоичном сбалансированном дереве (например, в декартовом дереве). Понятно, что для изменения в элементе небодимо обновить этот элемент в отрезках. Теперь рассмотрим запрос суммы. Понятно, что весь отрезок запроса мы можем разбить на отрезков, которые есть в дереве отрезков. Теперь для каждого такого отрезка нам необходимо найти сумму всех элементов, для которых верно x < ai < y. Это легко сделать с помощью двоичного сбалансиванного дерева (дополнительно храним и обновляем сумму на поддереве), в котором хранится весь этот отрезок.
Итого получаем на запрос и на обновление элемента.
Если запросы даны offline, то можно для каждой вершины дерева отрезка найти все значения, которые там будут в какой-либо момент, и сжать их (для каждой вершины свое сжатие). После этого мы можем использовать более "статическую" структуру, например, дерево Фенвика. Запрос будет тоже за O(log2n), но вроде константа бинпоиска (сжатие) + Фенвика меньше, чем у декартова дерева.
Хорошее замечание :)
В некоторых задачах, например, 785E - Антон и перестановка, без этого довольно сложно поместиться в ограничения по времени.