# Prefix Sum in Java

[TOC]

## Types

given `nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };`

1. prefix sum starting from `nums[0]`, with `prefixSum.length = nums.length`.
>`prefixSum = { 1, 3, 6, 10, 15, 21, 28, 36, 45 };`
2. prefix sum starting from `0`, with `prefixSum.length = nums.length + 1`.
>`prefixSum = { 0, 1, 3, 6, 10, 15, 21, 28, 36, 45 };`

## How to write (type1 as examples)

### 1. Using iteration

int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] prefixSum = new int[nums.length];
prefixSum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    prefixSum[i] = prefixSum[i - 1] + nums[i];
}

### 2. Using Arrays.setAll

int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] prefixSum = new int[nums.length];
Arrays.setAll(prefixSum, i -> i == 0 ? nums[0] : prefixSum[i - 1] + nums[i]);

### 3. Using Arrays.parallelPrefix

int[] nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] prefixSum = Arrays.copyOf(nums, nums.length);
Arrays.parallelPrefix(prefixSum, (x, y) -> x + y);

## Usage

### Interval Sum

prefixSum[j] - prefixSum[i];
// = sum of [i,j)

### Overlapped Intervals

Given a set of intervals `int[][] intervals`, where each interval is represented as `{ start, end, value }`, add value to all elements in the range `arr[start] to arr[end - 1]`.

Return an array `arr`, where `arr[i]` represents the accumulated sum of values at index i.

for (int[] interval : intervals) {
    int start = interval[0];
    int end = interval[1];
    int value = interval[2];
    
    arr[start] += value;
    arr[end] -= value;
}

// after prefix sum, we get the answer
for (int i = 1; i < arr.length; i++) {
    arr[i] += arr[i - 1];
}