정수 배열에서 하위 배열 합계를 찾습니다.

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은 2 차 알고리즘을 사용할만큼 충분히 작을 것입니다.

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})의 곱을 계산하십시오. k> 0 인 z^k의 계수는 k가 하위 배열 합인 경우에만 0이 아니므로 양의 계수가 아닌 0이 아닌 계수의 수를 읽어야합니다. 또한 z의 거듭 제곱은 -S에서 S까지이므로 S logS의 순서로 곱셈에 시간이 걸립니다.

Answer 2

하위 배열을 트리 형태로 볼 수 있습니다. 서브 어레이 [0,3]은 [0,1] 및 [2,3]으로 나눌 수 있다는 의미입니다.

그래서 노드가 부분 배열의 길이로 정의되고 원본 배열에서 오프셋이 시작되며 하위 배열을 계산할 때마다이 트리에 결과를 저장합니다.

하위 배열을 계산할 때이 트리에서 기존 계산 된 값을 확인할 수 있습니다.

또한 분할 할 때 어레이의 일부분을 다른 CPU 코어에서 계산할 수 있습니다.

이 솔루션은 사용자가 모든 값을 임시로 사용하지 않고 즉시 필요로하지 않는다고 가정합니다. 전자의 경우 더 똑똑한 해결책이 될 수 있습니다.

또한 저는 10000 년대 이상에있는 요소의 수에 대해 이야기하고 있다고 가정합니다. 그렇지 않으면, 그런 일은 좋은 운동이지만 실질적인 가치는별로 없습니다.