Участник:Vid1525

Алгоритм нахождения суммы чисел на отрезке с помощью одномерного "Дерево отрезков"
Последовательный алгоритм
Последовательная сложность	[math]O(qlog(n))[/math]
Объём входных данных	[math]n[/math]
Объём выходных данных	[math]q[/math]

Авторы: И.Д. Васенков

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

Sqlite https://www.sqlite.org/

SciPy https://scipy.org/

Sklearn https://scikit-learn.org/stable/

3 Литература

1. Bentley, J. L. (1979). "Decomposable searching problems".

2. Lueker, G. S. (1978). "A data structure for orthogonal range queries". 19th Annual Symposium on Foundations of Computer Science (sfcs 1978).

3. Lee, D. T.; Wong, C. K. (1980). "Quintary trees: A file structure for multidimensional database systems". ACM Transactions on Database Systems.