Всем привет. У меня появилось 2 вопроса, нагуглить которые эффективно я не смог, поэтому сюда напишу.
1. Может кто-нибудь дать ссылки на задачи на двумерное дерево отрезков?
2. Кто-нибудь может рассказать немного про квадродерево? Ну или хотя бы дать ссылки на толковые статьи, а то все, что я смог найти, так это описание в вики, да вот эта небольшая статейка. Суть я понял, но вот как именно строить все равно не очень понятно. Плюс нигде не могу найти внятной асимптотики. PavelKunyavskiy писал где-то, что работает за корень, на вики написано, что за log, а здесь вообще я не пойму, что значит "за O(N)".
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 8 | SecondThread | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 02.05.2024 00:08:51 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
На прошлой харьковской зимней школе были лекции про квадродерево. Можно попробовать там поискать в архиве
Имеется ввиду 2012 года? 2011 и 2010 я просмотрел, вроде нет таких лекций. А 2012 года на сайте нет.
Понятия КД-дерево и Квадро-Дерево нужно различать.
То, что работает за
, называется КД-деревом.
Возможно, имеется в виду моя лекция (Харьков-2012). Тогда текст можно найти здесь. Часть 4. Страница 5. Тема "КД-дерево". Видео лекции вроде гуглится...
В википедии сказано, что в среднем случае КД-дерево работает за
, а в худшем за O(N1 - 1 / k), где k — размерность пространства. Для k = 2 получаем ровно 
.
P.S. Здесь везде КД-дерево = структура данных, построенная от N точек. Если у нас есть таблица m × m, то N = m2, соответственно
= m.
Спасибо! Классная лекция, кстати.
Извиняюсь, не то.
Здесь есть задачи с харьковской зимней школы на двумерное дерево отрезков.
Здесь видео с прошлой харьковской зимней школы.
Его просто совсем недавно выложили.
O(N) в https://sites.google.com/site/indy256/algo/quad_tree означает временную сложность прямоугольного запроса count(x1, y1, x2, y2) на сетке NxN. Согласен, что написано непонятно.
Пример, на котором достигается N тут http://apps.topcoder.com/forums/?module=Message&messageID=1064330
Там рассматривается запрос в виде полоски шириной 1, который приводит к просмотру N клеток 1x1, например count(0, 0, N-1, 0).
Если я правильно понимаю, то хуже чем O(N) быть не может. А если мы заполним всю сетку NxN значениями, а запрос выполняется за O(N), то в этом случае вроде как получается, что запрос работает за корень.
Гипножаба
НЛО
За сколько оно работает зависит от конкретной задачи. За корень будет для множества точек на плоскости. (Правда видимо эта структура называется KD-дерево) По ссылке где непонятное "O(N)" насколько я понимаю речь идет про время работы за длину границы фигуры, на которой делается операция.