Prefix Sum Array

and their interesting properties along with implementation in Rust Language

Introduction

Prefix Sum Array is widely used in Competitive Programming for optimizing the solution, generally in arrays or vectors. Using Prefix Sum Array, we can perform Range Queries in constant, or O(1) time complexity.

In this article, we will discuss some interesting properties of prefix sum array, and see the code in Rust Language to build a prefix sum array.

Definition : Prefix sum array, p of an array a is defined such that every index of array p, contains sum of all elements of a upto that index.

Formally, for all 0 <= i < N,

p[i] = a[0] + a[1] + a[2]... + a[i-1] + a[i]

Interesting properties

1. i^th element of prefix sum array, p[i] = a[i]+p[i-1], for all 1 <= i < n
2. Prefix sum array of positive elements is always sorted, in ascending order.
3. If there are common element in prefix array, this means that sum of the subarray between them is 0.

Generate Prefix Array

Here is the function to generate a prefix array in Rust Language.

fn prefix_sum(array:&Vec<usize>)->Vec<usize>{

    // Initialize the array with all 0
    let mut prefix_array = vec![0; array.len()];

    // First element of prefix array is first element of array
    prefix_array[0] = array[0];

    // Generate prefix array using property
    // p[i] = a[i] + p[i-1]
    for i in 1..array.len() {
        prefix_array[i] = prefix_array[i-1]+array[i];
    }

    return prefix_array;
}

With driver code

fn prefix_sum(array:&Vec<usize>)->Vec<usize>{

    // Initialize the array with all 0
    let mut prefix_array = vec![0; array.len()];

    // First element of prefix array is first element of array
    prefix_array[0] = array[0];

    // Generate prefix array using property
    // p[i] = a[i] + p[i-1]
    for i in 1..array.len() {
        prefix_array[i] = prefix_array[i-1]+array[i];
    }

    return prefix_array;
}

// Driver code

fn main() {
    let arr = vec![1, 2, 3, 4, 5, 6, 7];
    println!("{:?}", prefix_sum(&arr));
}

Output

[1, 3, 6, 10, 15, 21, 28]

Time Complexity : O( n )
Space Complexity : O( n )

Uses of Prefix Sum Array

1. Range Queries : By using prefix sum array, the Range Queries such as find sum of elements from [l, r] can be done in constant or O(1) time complexity.
2. Subarray with 0 sum : In prefix array, if there is any repeating element, that means that the sum of that subarray is 0.

and so on...

Conclusion

Prefix Sum Array is widely used in Competitive Programming for optimizing the solution, generally in arrays or vectors.

In this article, we discussed various properties and applications of prefix sum array and saw how to implement it in Rust Language.

Here is the function for easy access

fn prefix_sum(array:&Vec<usize>)->Vec<usize>{
    let mut prefix_array = vec![0; array.len()];
    prefix_array[0] = array[0];
    for i in 1..array.len() { prefix_array[i] = prefix_array[i-1]+array[i]; }
    return prefix_array;
}

Thank You