Массив суммы суффиксов

Опубликовано: 17 Сентября, 2022

Suffix Sum ArrayДав массив arr[] размера N , задача состоит в том, чтобы вычислить и вернуть его суффиксный массив sum .

Suffix Sum is a precomputation technique in which the sum of all the elements of the original array from an index i till the end of the array is computed.

Therefore, this suffix sum array will be created using the relation: 

Примеры:

Input: arr[] = { 15, 10, 25, 5, 10, 20 } , N = 6
Output: suffixSum[] = { 85, 70, 60, 35, 30, 20}
Explanation: While traversing the array from back, keep adding element from the back with element at current index.
suffixSum[5] = 20,  
suffixSum[4] =suffixSum[5] + arr[4] = 20+10 = 30 ,  
suffixSum[3] = suffixSum[4] + arr[3] = 30+5 = 35 and so on.

Input: arr[] = {10, 14, 16, 20}, n = 6
Output: suffixSum[] = {60, 50, 36, 20}
Explanation: suffixSum[3] = 20,  
suffixSum[2] =suffixSum[3] + arr[2] = 20+16 = 36 ,  
suffixSum[1] = suffixSum[2] + arr[1] = 36+14 = 40 and so on.

Подход : Чтобы заполнить массив сумм суффиксов, мы проходим через индекс N-1 до 0 и продолжаем добавлять текущий элемент с предыдущим значением в массив сумм суффиксов.

  • Создайте массив размера N для хранения суммы суффиксов.
  • Инициализировать последний элемент массива сумм суффиксов последним элементом исходного массива.
    суффиксСумма[n-1] = обр[n-1]
  • Пройдите исходный массив от N-2 до 0
    • Для каждого индекса я нахожу сумму суффикса и сохраняю ее в suffixSum[i]
    • suffixSum[i] = suffixSum[i + 1] + arr[i]
  • Возвратите вычисленный массив суммы суффикса.

Ниже приведена реализация описанного выше подхода для создания массива сумм суффиксов:


Сложность времени : O(N), чтобы пройти исходный массив для вычисления суммы суффиксов.
Вспомогательное пространство : O(N) для хранения массива сумм суффиксов.

РЕКОМЕНДУЕМЫЕ СТАТЬИ