Постановка задачи

Пусть дан массив, состоящий из N целых чисел (для определенности: пусть нумерация начинается с нуля).

К массиву ожидается достаточно большое количество запросов. Каждый запрос требует нахождении суммы элементов на интервале [left; right] (где left и right – номера самого левого и самого правого элемента, включительно).

Требуется создать такую структуру данных и метод работы с ней, чтобы скорость ответа на такой запрос была выше, чем у тривиального алгоритма.

Идея реализации

Разобьем массив на блоки, длины ceil(sqrt n), где ceil() – операция округления до ближайшего сверху целого. Таких блоков будет ровно sqrt n.

Для каждого блока вычислим сумму элементов в нем, и запишем в массив block_sum[].

Теперь ответ на запрос о сумме элементов на интервале можно получить за время O(sqrt n).

Если какой-то блок целиком принадлежит интервалу, можно использовать уже готовую сумму этого блока.

Если на интервале лежит только часть блока, к этой части можно применить тривиальный алгоритм подсчета суммы.

При этом, неполных блоков будет не более двух (первый и последний).

В худшем случае, для расчета суммы по каждому из неполных блоков требуется sqrt n - 1 операция.

Также, в худшем случае, потребуется суммирование sqrt n - 2 блоков.

Пример работы алгоритма

Пусть дан массив из 9 элементов. Тогда длина блока будет равна 3, количество блоков также будет 3.

В случае, если потребуется вычислить сумму элементов на интервале [1; 7] (как показано на рисунке).

table
    Будут сделаны следующие вычисления:
  • Первый блок входит в запрашиваемый интервал не полностью, поэтому для него будет использован тривиальный алгоритм: 2 + 1 = 3 (сумма элементов из первого блока);
  • Второй блок находится на интервале, поэтому сумма его элементов уже известна и равна 14;
  • Третий блок входит в интервал частично, поэтому сумму в нем будем также считать поэлементно: 7 + 4 = 11.

Итого: 3 + 14 + 11 = 28.

Реализация

int a[100]; int block_sum[10]; int n; // пропустим ввод данных: массив a[], количество элементов n // пропустим предварительную запись нулей во все элементы // массива block_sum[] // размер блока, он же – количество блоков int block_size = ceil( sqrt(n) ); int block_count = block_size; // Выполним подсчет сумм элементов в каждом блоке for (int i = 0; i < n; i++) block_sum[ i / block_size ] = block_sum[ i / block_size ] + a[ i ]; // цикл обработки запросов while (запросы не закончились) { cin >> left >> right; sum = 0; // найдем, в какой блок попадают границы интервала left_b = left / block_size; right_b = right / block_size; if (left_b == right_b) { for (int i = left; i<=right; i++ ) sum = sum + a[ i ]; } else { //вычисляем, где кончаются данные в первом блоке // и начинаются в последнем, // так как эти блоки требуется обрабатывать поэлементно left_end = ( left_b + 1 ) * block_size - 1; right_start = right_b * block_size; // поэлементная обработка самого левого блока for (int i = left; i <= left_end; i++) sum = sum + a[ i ]; // поблочная обработка средних блоков, // которые целиком принадлежат интервалу for (int i = left_b + 1 ; i <= right_b - 1; i++) sum = sum + block_sum[ i ]; // поэлементная обработка самого правого блока for (int i = right_start; i <= right; i++) sum = sum + a[ i ]; } cout << sum; }
Последнее изменение: Суббота, 15 Август 2020, 02:34