Теоремы

ТЕОРЕМА О КОРРЕКТНОСТИ 2D OVERLAP-QUERY: Если операция идемпотентна, то четыре угловых блока размера 2^kr x 2^kc дают правильный ответ на статическом half-open прямоугольнике.
ТЕОРЕМА О КОРРЕКТНОСТИ ЗАПРОСА ЧЕРЕЗ ПЕРЕКРЫВАЮЩИЕСЯ БЛОКИ: Если операция идемпотентна, то два перекрывающихся блока длины 2^k, выбранные по k = floor(log2(length)), дают правильный ответ на статическом отрезке [left, right].
ТЕОРЕМА О КОРРЕКТНОСТИ ПО ИНВАРИАНТУ ЦИКЛА: Если инвариант верен до цикла, сохраняется каждой итерацией и вместе с условием завершения дает постусловие, то цикл частично корректен.
ТЕОРЕМА О КОРРЕКТНОСТИ KD OVERLAP-QUERY: Если операция идемпотентна, то 2^d угловых гиперблоков, выбранных по level-вектору, дают правильный ответ на статическом half-open гиперпрямоугольнике.
ТЕОРЕМА О РАВЕНСТВЕ МНОЖЕСТВ К статье: Два множества равны тогда и только тогда, когда каждое из них является подмножеством другого.
ТЕОРЕМА О РАЗЛОЖЕНИИ ОБЪЕДИНЕНИЯ МНОЖЕСТВ К статье: Объединение двух множеств можно разложить на элементы, принадлежащие только первому множеству, только второму множеству, и элементы, принадлежащие обоим множествам.
ТЕОРЕМА ОБ АМОРТИЗИРОВАННОЙ СТОИМОСТИ APPEND В ДИНАМИЧЕСКОМ МАССИВЕ: Если динамический массив увеличивает вместимость геометрически при переполнении, то последовательность из n операций append выполняется за O(n), поэтому амортизированная стоимость одного append равна O(1).
MASTER THEOREM: Для рекуррентностей вида T(n) = aT(n/b) + f(n) асимптотика определяется сравнением f(n) с n^(log_b a) при выполнении условий теоремы.