Количество K в массиве для заданного диапазона индексов после обновления массива для запросов Q

Дан массив arr[] из N целых чисел, целое число K и Q запросов типа, как описано ниже:

• (1, L, R) : если запрос имеет тип 1 , найдите количество K в диапазоне [L, R] .
• (2, P, X) : если запрос имеет тип 2 , то обновить элемент массива с индексом P до X .

Задача состоит в том, чтобы выполнить запросы к заданному массиву и соответствующим образом распечатать результат.

Примеры:

Input: K = 0, arr[] = {9, 5, 7, 6, 9, 0, 0, 0, 0, 5, 6, 7, 3, 9, 0, 7, 0, 9, 0}, query[][2] = {{1, 5, 14 }, {2, 6, 1 }, {1, 0, 8 }, {2, 13, 0 }, {1, 6, 18 } }
Output: 5
3
6
Explanation: 
Following are the values of queries performed: 
 

1. first query is of type 1, then the count of 0s(= K) in the range [5, 14] is 5.
2. second query is of type 2 so update the value of array element at index P = 6 to X = 1 i.e., arr[6] = 1. 
   The modified array is {9 5 7 6 9 0 1 0 0 5 6 7 3 9 0 7 0 9 0}.
3. third query is of type 1, then the count of 0s(= K) in the range [0, 8] is 3.
4. fourth query is of type 2 so update the value of array element at index P = 13 to X = 0 i.e., arr[13] = 0. 
   The modified array is {9 5 7 6 9 0 1 0 0 5 6 7 3 0 0 7 0 9 0}.
5. fifth query is of type 1, then the count of 0s in the range [6, 18] is 6.

Therefore, print 5, 3, and 6 as the answer to the queries.

 

Input: K = 6, arr[] = {9, 5, 7, 6}, query[][2] = {{1, 1, 2}, {2, 0, 0} }
Output: 0

 

Наивный подход: самый простой подход к решению данной проблемы состоит в том, чтобы изменить элемент массива для запроса второго типа и для первого типа запроса, пройти массив по диапазону [L, R] и вывести количество K в Это.

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, используя дерево сегментов для расчета количества Ks от начального индекса до конечного индекса, временная сложность для этого запроса в дереве сегментов составляет O(log(N)) . Чтобы изменить значение и обновить дерево сегментов, обновите дерево сегментов за время O(log(N)) . Выполните следующие шаги, чтобы решить данную проблему:

• Определите функцию Build_tree , которая рекурсивно вызывает себя один раз для левого или правого потомка или дважды, один раз для левого и один раз для правого потомка (например, разделяй и властвуй).
• Определите частоту функции, аналогичную функции Build_tree , и найдите сумму количества Ks .
• Определите функцию update , которая передает текущую вершину дерева и рекурсивно вызывает себя с одной из двух дочерних вершин, а после этого пересчитывает свое нулевое значение счетчика, аналогично тому, как это делается в методе Build_tree .
• Инициализируйте вектор seg_tree и вызовите функцию Build_tree , чтобы построить начальное дерево сегментов.
• Переберите диапазон [1, Q], используя переменную i , и выполните следующие шаги:
  • Если тип текущего запроса равен 1, то вызовите функцию frequency(1, 0, n-1, l, r, seg_tree) для подсчета частоты Ks.
  • В противном случае обновите значение в массиве arr[] и вызовите функцию update(1, 0, n-1, pos, new_val, seg_tree), чтобы обновить значение в дереве сегментов.

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

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