Решение задачи проще понять для одномерного случая, то есть для матрицы размерностью 1хN. Подсчет количества телефонов сразу на всех интервалах 0≤I≤N-1, легко выполняется за O(N) операций, и все полученные результаты следует сохранить в таблице. Тогда ответ на запрос о количестве телефонов в некотором интервале [X, Y] можно получить следующим образом: Sxy=Sy-Sx-1, Sy - количество телефонов на интервале [0, Y], а Sx-1 - на интервале [0, X-1]. То есть подобный запрос выполняется за O(1) операций. При изменении количества телефонов в каком-либо квадрате таблица сумм телефонов пересчитывается за O(N) действий.
Однако, если вспомогательные суммы хранить в виде специального дерева, то обновлять их можно за O(logN) операций. Хранить же такое, хотя и не бинарное, дерево можно с помощью одномерного массива из N элементов, индексы которого удобно обозначать от 1 до N. I-й элемент такого массива содержит сумму элементов исходного массива на интервале [I-2k, I-1], где за k мы всегда будем обозначать число нулей в конце двоичного представления индекса элемента вспомогательного массива. Например, в четвертом элементе вспомогательного массива хранится сумма элементов с 0-го по 3-й исходного массива, так как 4=1002, то есть два нуля в конце двоичного представления, и I-2k=4-22=0, а в шестом элементе - сумма только четвертого и пятого элементов, так как 6=1102 и I-2k=6-21=4. Обновляется вспомогательный массив так. Если какой-то элемент исходного массива изменился, то также меняется и соответствующий элемент вспомогательного массива. Индекс следующего элемента вспомогательного массива, который тоже следует изменить вычисляется следующим образом: к индексу текущего элемента прибавляется 2k. Например, если на 3 увеличилось количество телефонов в квадрате 2 (он третий по счету), то сначала на 3 увеличивается 3-й элемент массива, затем на три же 4-й (3=112, k=0, 3+20=4), затем 8-й (4=1002, k=2, 4+22=8) и т. д. Так как значение k на каждом шаге увеличивается, обновление массива производится за O(logN) действий. Сумму же элементов на любом интервале [0, I-1] c помощью построенного дерева можно подсчитать так. Начинаем с элемента вспомогательного массива с индексом I. Следующий элемент дерева, который следует включить в сумму вычисляется как I-2k и так далее пока не дойдем до 0 (нулевого элемента у нас в дереве нет). Например, сумма элементов на интервале [0, 6] вычисляется как сумма элементов дерева с индексами 7, 6 и 4 (7=1112, k=0, 7-20=6; 6=1102, k=1, 6-21=4; 4=1002, k=2, 4-22=0).
Такая операция производится также за O(logN) действий. А запрос относительно количества телефонов на любом интервале, как уже было показано выше, выполняется за две такие операции. Следовательно, любая команда из условия задачи для одномерного случая выполнима не более чем за O(logN) действий. Заметим также, что массив со значениями телефонов в каждом квадрате можно не хранить. Достаточно иметь массив для хранения описанного дерева сумм.
Решение для одномерного случая может быть распространено на двумерный случай следующим образом. Нам потребуется построить дерево деревьев, имеющих структуру аналогичную описанной выше и хранить его в квадратном массиве, по размеру и индексам совпадающем с исходным, исходный же массив хранить не будем. Тогда элемент [X-1, Y-1] такой древообразной структуры содержит сумму элементов в области, размер которой определяется количеством конечных нулей в двоичном представлении X и Y. Такая структура позволяет подсчитывать сумму телефонов в прямоугольнике [0, X]x[0, Y] за O((logN)2) действий.
Запрос о количестве телефонов в любой прямоугольной области можно выполнить за 4 подобных операции: sum([L, R]x[B, T])= sum([0, R]x[0, T]) - sum([0, L-1]x[0, T]) - sum([0, R]x[0, B-1]) + sum([0, L-1]x[0, B-1]).
Шенгенская виза во Францию, стоимость оформления. Руководство по визам во Францию. . Предлагаем качественное изготовление печатей . NO APB "Gruppa R" охрана заказывайте у нас. . Построенные дома из дерева фото и отзывы заказчиков.
