Вопросы с тегом «intervals»

11
Структура данных для карты по интервалам

Пусть nnn будет целым числом, и пусть ZZ\mathbb{Z} обозначает множество всех целых чисел. Обозначим через [a,b][a,b][a,b] интервал целых чисел {a,a+1,a+2,…,b}{a,a+1,a+2,…,b}\{a,a+1,a+2,\dots,b\} . Ищу структуру данных для представления отображения f:[1,n]→Zf:[1,n]→Zf:[1,n] \to \mathbb{Z} . Я хочу,...

10
Доказательство сложности времени для реализации дерева ранжированных сумм в дереве сегментов

Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AAAO(logn)O(log⁡n)\mathcal{O}(\log n) Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие...