Алгоритмы и структуры данных

@Dag0n · Регистрация: 07.04.2021

Author24 — интернет-сервис помощи студентам

Здравствуйте господа, наткнулся в интернетах на следующие пункты:
Segment tree:
-answers each query in O(logN)
-preprocessing done in O(N)
-Pros: good time complexity.
-Cons: larger amount of code compared to the other data structures.

Fenwick tree :
-answers each query in O(logN)
-preprocessing done in O(NlogN)
-Pros: the shortest code, good time complexity
-Cons: Fenwick tree can only be used for queries with L=1, so it is not applicable to many problems.
Подскажите пожалуйста, какие пункты можно добавить декартову дереву, если добавить его в это сравнение?

@lemegeton · 23.12.2022, 19:29

Это есть прямо в википедии.
Построение O(n)
Поиск O(log(n))
Вставка O(log(n))
Удаление O(log(n))

@Dag0n 0 / 0 / 0 Регистрация: 07.04.2021 Сообщений: 5
		1
	Алгоритмы и структуры данных 23.12.2022, 19:05. Показов 279. Ответов 1 Метки декартово дерево, дерево отрезков, структуры данных (Все метки) Здравствуйте господа, наткнулся в интернетах на следующие пункты: Segment tree: -answers each query in O(logN) -preprocessing done in O(N) -Pros: good time complexity. -Cons: larger amount of code compared to the other data structures. Fenwick tree : -answers each query in O(logN) -preprocessing done in O(NlogN) -Pros: the shortest code, good time complexity -Cons: Fenwick tree can only be used for queries with L=1, so it is not applicable to many problems. Подскажите пожалуйста, какие пункты можно добавить декартову дереву, если добавить его в это сравнение? 0

@lemegeton 4863 / 2662 / 913 Регистрация: 29.11.2010 Сообщений: 5,743
	23.12.2022, 19:29	2
	Это есть прямо в википедии. Построение O(n) Поиск O(log(n)) Вставка O(log(n)) Удаление O(log(n)) 0