| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Здравствуйте,
Возникла проблема при решении задачи из тренировки 2013-2014 СПбГУ В 6 Дерево Фенвика, В("Звёзды"). Коды закрыты, но может кто-нибудь помочь с идеей решения? Я пробовал вот так, но это неправильно. Ведь необходимо реализовать трехмерное дерево?
Дерево Фенвика, в вашем случае, отвечает на запрос суммы на прямоугольном параллелепипеде с начальной точкой (0, 0, 0). Подумайте как с помощью таких запросов научиться отвечать на запрос суммы в произвольном прямоугольном параллелепипеде. Рекомендую сначала разобраться, как решать такую задачу в двумерном случае.
Hint: Вам поможет формула включений-исключений.
Можете объяснить, как здесь почему используется формула включений-исключений? В двумерном случае можно и без нее обойтись, а здесь как ?
Может я чего-то глобально не понимаю, но как Вы это делаете в двумерном случае без использования чего-то похожего на формулу включения-исключения?
По моему , та формула намного легче , и до нее можно додуматься самому.А вот в трехмерном случае...
Суть остается той же. При подсчете суммы Вы некоторые элементы считаете дважды, трижды и так далее... Чтобы все правильно учесть, просто применим формулу включений-исключений и получим ответ. И хорошо понимать, что в том, что Вы хотите получить будут присутствовать такие слагаемые вида sum(XX, YY, ZZ), где XX может быть x1 - 1 или x2, YY — y1 - 1 или y2 и ZZ — z1 - 1 или z2. То есть всего 8 штук. Осталось всего лишь найти коэффициенты.
Вроде понял) Большое спасибо)