@N
Не, код не нужен. Просто нужно, чтобы читатель понимал, почему это вообще работает и как, и где можно подкрутить
https://habr.com/ru/post/566248/
Рано ее опубликовали, к сожалению, нужно было немного доработать(
Size: a a a
2021 July 05
q
V
И то крутяк
P
А какая будет сложность в наихудшем случае для запроса в таком дереве? Тоже O(N)?
P
То есть главный метод по поиску количества точек выглядит как-то так, но я не совсем понимаю, насколько здесь возможно получить O(N).
Тип мы уходим в две ветки, тогда когда наш круг пересекает текущий прямоугольник, но насколько возможно, что мы так будем разветвлятся на каждой ноде...
Тип мы уходим в две ветки, тогда когда наш круг пересекает текущий прямоугольник, но насколько возможно, что мы так будем разветвлятся на каждой ноде...
DP
сбалансированное дерево без пересечений O(log N)
иначе O(N)
можешь позаботится чтобы при каждом добавлении или удалении ноды дерево балансировалось и пересечения убирались
иначе O(N)
можешь позаботится чтобы при каждом добавлении или удалении ноды дерево балансировалось и пересечения убирались
P
удаления и добавления нету - я строю по медиане. Множество точек известно наперёд
P
без пересечений это хз как - нужно загуглить
DP
строй добавляя по 1 элементу за раз.
P
Это чтобы избежать пересечений?
DP
DP
а, у тебя кубы а не точки?
P
точки
DP
точки можно хранить без пересечений
P
Ну то есть я храню в каждой ноде дополнительно прямоугольник, который она покрывает, что ускорять запрос на поиск количества точек в заданном круге центром и радиусом.
P
"Тип мы уходим в две ветки, тогда когда наш круг пересекает текущий ограничивающий прямоугольник, но насколько возможно, что мы так будем разветвлятся на каждой ноде..."
Но все равно же возможен такой кейс
Но все равно же возможен такой кейс
P
То есть там же не будет всегда O(log(N)) из-за этого.
P
Вообще вот, если интересно - https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle/discuss/1182879/Optimized-K-D-tree-Solution-from-the-follow-up-STL-C++
Я ещё тогда написал пост, но просто сейчас затригерили вопросом про complexity, и я подумал, гарантируется ли там всё-таки O(log(N)) worst case...
Я ещё тогда написал пост, но просто сейчас затригерили вопросом про complexity, и я подумал, гарантируется ли там всё-таки O(log(N)) worst case...
VK
Всем привет! Можете подсказать алгоритм поиска всех комбинаций подстрок в строке. Например, есть строка
результат будет 6:
Есть ли какая формула для расчета или алгоритм какой?
abcрезультат будет 6:
a
b
c
ab
bc
abc
Есть ли какая формула для расчета или алгоритм какой?
q
При строке 'ааа' какой вывод?