Сумма произведений всех неупорядоченных пар в заданном диапазоне с запросами на обновление

Учитывая массив A[] , состоящий из N целых чисел и Q запросов следующих типов, задача состоит в том, чтобы распечатать вывод для всех запросов на обновление.

• (1, L, R): 1-й тип запроса для нахождения суммы произведения всех неупорядоченных пар от индекса L до R в массиве, где 1 <= L <= R <= N .
• (2, P, X): 2-й тип запроса на изменение значения P ^-го целого числа массива на новое значение X .

Пример:

Input: A[] = {5 7 2 3 1}, Q = 3, Queries[] = [ [1, 1, 3], [2, 2, 5], [1, 2, 5]] 
 

Output: 
59
41
Explanation: 
Query 1: In the 1st query, the possible pairs in the given range are (5, 7), (5, 2) and (7, 2). So the pairwise product sum will be (5*7) + (5*2) + (7*2) = 35 + 10 + 14 = 59. 
Query 2: In the 2nd query, update the 2nd integer to 5, which makes the array as [5, 5, 2, 3, 1]. 
Query 3: In the 3rd query, the possible pairs in range [2, 5] are (5, 2), (5, 3), (5, 1), (2, 3), (2, 1), and (3, 1). The sum of product of these pairs is 41.

Input: A[] = {7 3 2 1 4 5 8}, Q = 5, Queries[] = [ [1, 1, 6], [2, 2, 4], [1, 2, 5], [2, 3, 8], [1, 4, 7]] 
 

Output: 59 
41 
6

Наивный подход: простой способ решить эту проблему — для 1-го типа запроса сгенерировать все неупорядоченные пары в заданном диапазоне запроса и вывести сумму произведения этих пар. Для 2-го типа запросов обновите элемент массива в соответствии с заданным значением.

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

Временная сложность: O(N ² ) для запроса попарной суммы произведений и O(1) для запроса на обновление.
Космическая сложность: O(N)

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

Лучший подход. Лучший подход к дальнейшему снижению сложности — использование дерева Фенвика на основе следующих наблюдений:

Given that 
(a + b + c)² = a² + b² + c² + 2*(a*b + b*c + c*a)
Let required Pairwise Product Sum be P
Let E = (a1 + a2 + a3 + a4 … + an)² 
=> E = a1² + a2² + … + an² + 2*(a1*a2 + a1*a3 + ….) 
=> E = a1² + a2² + … + an² + 2*(P) 
=> P = ( E – (a1² + a2² + …. + an²) ) / 2
So, P = (E – Q)/2 where Q = (a1² + a2² + …. + an²) 

Согласно приведенному выше наблюдению, мы можем поддерживать два дерева Фенвика.

• Первое дерево Фенвика будет отслеживать сумму элементов в заданном диапазоне с помощью запросов на обновление. Это можно использовать для расчета E для любого заданного диапазона.
• Точно так же второе дерево Фенвика будет отслеживать сумму квадратов элементов в заданном диапазоне с помощью запросов на обновление. Это можно использовать для расчета Q для любого заданного диапазона. После этого P можно легко рассчитать как P = (E – Q)/2 .

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

Временная сложность: O (N * log N) для построения дерева Фенвика.
O (log N) для запроса суммы попарных произведений
O(log N) для запроса на обновление.
Вспомогательное пространство: O(N)