Поиск суммы подматрицы в целочисленном массиве

Question

Учитывая массив из N положительных целых чисел. Он может содержать поддиапазоны n*(n+1)/2, включая одноэлементные подматрицы. Каждая подматрица имеет сумму S. Найти S's для всех подматриц, очевидно, O(n^2), так как количество подмассивов O(n^2). Можно также повторить много сумм S's. Есть ли способ найти количество всех различных сумм (а не точные значения сумм, но только счет) в O(n logn).

Я пробовал подход, но застрял в пути. Я повторил массив из индекса 1 в n.
Скажем a[i] - данный массив. Для каждого индекса i, a[i] будет добавлен ко всем суммам, в которых участвует a[i-1], и будет включать себя также как отдельный элемент. Но дубликат появится, если среди сумм, в которых участвует a[i-1], разница в двух суммах равна a[i]. Я имею в виду, что, например, суммы Sp и Sq заканчиваются на a[i-1], а разница составляет a[i]. Затем Sp + a[i] равно Sq, что дает Sq как дубликат.

Скажите C[i] - количество отличных сумм, в которых заканчивается a[i].
So C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i].

Но проблема заключается в том, чтобы найти часть числа пар в O(log n). Пожалуйста, дайте мне некоторый намек на это или если я ошибаюсь, и совершенно другой подход требует проблемного момента.

Answer 1

Когда S не слишком велико, мы можем считать отдельные суммы одним (быстрым) полиномиальным умножением. Когда S больше, N, мы надеемся, достаточно мал, чтобы использовать квадратичный алгоритм.

Пусть x_1, x_2, ..., x_n - элементы массива. Пусть y_0 = 0 и y_i = x_1 + x_2 + ... + x_i. Пусть P (z) = z^{y_0} + z^{y_1} + ... + z^{y_n}. Вычислить произведение многочленов P (z) * P (z^{- 1}); коэффициент при z^k с k> 0 отличен от нуля тогда и только тогда, когда k является суммой подматрицы, поэтому нам просто нужно прочитать число ненулевых коэффициентов положительных степеней. Более того, степени z варьируются от -S до S, поэтому умножение занимает время порядка S log S.

Answer 2

Вы можете посмотреть на подматрицы в виде своего рода дерева. В том смысле, что подмассива [0,3] можно разделить на [0,1] и [2,3].

Итак, создайте дерево, где узлы определены длиной подмассива и его смещением в исходном массиве, и всякий раз, когда вы вычисляете подмассиву, сохраните результат в этом дереве.

При вычислении подматрицы вы можете проверить это дерево для существующих предварительно вычисленных значений.

Кроме того, при разделении части массива могут вычисляться на разных ядрах ЦП, если это имеет значение.

Это решение предполагает, что вам не нужны все значения сразу, а не специальные. Для первого может быть разумное решение.

Кроме того, я предполагаю, что мы говорим о подсчетах элементов в 10000 и более. В противном случае такая работа является хорошим упражнением, но не имеет практической ценности.