Сумма нечетных элементов массива после каждого запроса на обновление

Опубликовано: 25 Февраля, 2023

Дан целочисленный массив Arr[] длины N и массив Queries[] длины Q , где Queries[i] = [значение i , индекс i ]. Для каждого запроса i обновите Arr[index i ] = Arr[index i ] + value i , затем выведите сумму всех нечетных значений Arr[].

Примеры:

Input: N = 4, Arr = [1,2,3,5], Q = 4, Queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: 8 7 7 9
Explanation: At the beginning, the array is [1,2,3,5].
After adding 1 to Arr[0], the array is [2,2,3,5], and the sum of odd values is 3 + 5 = 8.
After adding -3 to Arr[1], the array is [2,-1,3,5], and the sum of odd values is -1 + 3 + 5 = 7.
After adding -4 to Arr[0], the array is [-2,-1,3,5], and the sum of odd values is -1 + 3 + 5 = 7.
After adding 2 to Arr[3], the array is [-2,-1,3,7], and the sum of odd values is -1 + 3 + 7 = 9.

Input: N = 1 , Arr = [1], Q = 1,Queries = [[4,0]]
Output: [5]
Explanation: At the beginning, the array is [1].
After adding 4 to Arr[0], the array is [5], and the sum of odd values is 0.

Наивный подход: проблема может быть решена путем реализации упомянутых операций.

For each query first update the value and then iterate through the array to find the sum of odd integers.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Объявите массив ответов.
  • Запустите цикл от j = 0 до Q-1 :
    • Увеличить arr[idx] (где idx — индекс, указанный в запросе) на заданное значение в запросе.
    • Инициализировать сумму до 0.
    • Запустите вложенный цикл от i = 0 до N-1 :
      • Если элемент нечетный, добавьте это значение к сумме.
      • Добавьте сумму в массив ответов.
  • Распечатайте массив ответов.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(Q*N).
Вспомогательное пространство: O(Q) т.е. массив ответов размера Q.

Эффективный подход с использованием предварительного вычисления:

Задача может быть решена с помощью предварительного вычисления, основанного на следующем наблюдении:

Say the sum of odd elements was S before performing an update query. So, for update query, there can be four cases:

  • Element changes from odd to odd: In this case the sum increases by value (where value is the amount needed to be updated as per the query). This can be interpreted as subtracting the previous value from S and then adding the new updated value.
  • Element changes from even to odd: In this case the increase in sum is the same as the new odd value.
  • Element changes from odd to even: In this case the sum decreases by an amount same as the previous value of the element.
  • Element changes from even to even: In this case there is no change in sum.

So we can see that whenever the element was odd before update, initially there is a decrement in the sum and if the new updated value is odd, there is an increment of that amount in S.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

  • Объявите массив ответов.
  • Итерация по всему массиву и вычисление суммы нечетных значений.
  • Запустите цикл от j = 0 до Q-1 :
    • Сохраните предыдущее значение Arr[index j ] во временной переменной.
    • Если значение temp нечетное, уменьшите сумму на temp .
    • Увеличение значения Arr[index j ] на значение j и обновление temp .
    • Если значение temp нечетное, увеличьте сумму на temp .
  • Вставьте сумму в массив ответов.
  • Распечатайте массив ответов.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(max(Q, N)).
Вспомогательное пространство: O(Q) т.е. массив ответов размера Q.

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