Home
C++ Range Sum Query on Immutable Array via Prefix Sum
Tags:, , , ,

C++ Range Sum Query on Immutable Array via Prefix Sum

December 23, 2015 2 Comments algorithms, c / c++, math

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2): 1
sumRange(2, 5): -1
sumRange(0, 5): -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

Basically, we have an integer array and we want to be able to query the interval sum given two indices (i lower or equal than j), as fast as possible.

O(n^2) Bruteforce Algorithm to Compute Range Sum Query

We can compute the range sum at each query runtime. This bruteforce solution takes O(N^2) quadratic time and is inefficient.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class NumArray {
public:
    NumArray(vector<int> &nums) {
        int len = nums.size();
        sum = new int*[len];
        for (int i = 0; i < len; i ++) {
            sum[i] = new int[len];
        }
        for (int i = 0; i < len; i ++) {
            int k = 0;
            for (int j = i; j < len; j ++) {
                k += nums[j];
                sum[i][j] = k;
            }
        }
    }
 
    int sumRange(int i, int j) {
        return sum[i][j];
    }
private:
    int **sum;   
};
class NumArray {
public:
    NumArray(vector<int> &nums) {
        int len = nums.size();
        sum = new int*[len];
        for (int i = 0; i < len; i ++) {
            sum[i] = new int[len];
        }
        for (int i = 0; i < len; i ++) {
            int k = 0;
            for (int j = i; j < len; j ++) {
                k += nums[j];
                sum[i][j] = k;
            }
        }
    }

    int sumRange(int i, int j) {
        return sum[i][j];
    }
private:
    int **sum;   
};

Using Prefix Sum to Compute Range Query

Base on the following:

1
2

sum(i, j) = sum(0, j) - sum(0, i - 1); // for i > 0
sum(0, j) are pre-computed.
sum(i, j) = sum(0, j) - sum(0, i - 1); // for i > 0
sum(0, j) are pre-computed.

We can pre-compute the prefix sum in O(N) time and O(N) space. And we can compute the range sum based on the prefix sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

typedef unsigned long long int64;
 
class NumArray {
public:
    NumArray(vector<int> &nums) {
        int len = nums.size();
        sum = new int64[len];
        int k = 0;
        for (int i = 0; i < len; i ++) {
            k += nums[i];
            sum[i] = k;
        }
    }
 
    int sumRange(int i, int j) {
        if (i == 0) {
            return sum[j];
        }
        if (j == 0) {
            return sum[0];
        }
        return sum[j] - sum[i - 1];
    }
    
    ~NumArray() {
        delete [] sum;
    }
private:
    int64 *sum;
};
 
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);
typedef unsigned long long int64;

class NumArray {
public:
    NumArray(vector<int> &nums) {
        int len = nums.size();
        sum = new int64[len];
        int k = 0;
        for (int i = 0; i < len; i ++) {
            k += nums[i];
            sum[i] = k;
        }
    }

    int sumRange(int i, int j) {
        if (i == 0) {
            return sum[j];
        }
        if (j == 0) {
            return sum[0];
        }
        return sum[j] - sum[i - 1];
    }
    
    ~NumArray() {
        delete [] sum;
    }
private:
    int64 *sum;
};

// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Range Query via Prefix Sum:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
484 words
Last Post: Case Study: use PHPQuery to Crawl 3000 images from Tumblr
Next Post: Simple Steps Make Website Mobile Friendly (Responsive Design)?

The Permanent URL is: C++ Range Sum Query on Immutable Array via Prefix Sum

Related posts:

  1. Teaching Kids Programming – Depth First Search Algorithm to Compute the Max Width of a Binary Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary tree root, return...
  2. Teaching Kids Programming – High Accuracy Multiplication Algorithm (Multiply Strings) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two non-negative integers num1 and...
  3. WordPress Hosting Services You Can’t DIY If you happen to be using WordPress for your website, there’s no doubt that you’re...
  4. SQL Coding Exercise – Delete Duplicate Emails Write a SQL query to delete all duplicate email entries in a table named Person,...
  5. The USB Flash Benchmark Tool – FlashBench Previously, it is recommended that the USBCheck can be quite helpful in checking the quality...
  6. Teaching Kids Programming – Form Smallest Number From Two Digit Arrays (Set Intersection) Teaching Kids Programming: Videos on Data Structures and Algorithms Given two arrays of unique digits...
  7. Algorithms to Find the Missing Element in Sorted Array Given a sorted array A of unique numbers, find the K-th missing number starting from...
  8. Recursive Depth First Search Algorithm to Compute the Sum of Nodes with Even-Valued Grandparent in a Binary Tree Given a binary tree, return the sum of values of nodes with even-valued grandparent. (A...

2 Comments

  1. slyy2048

    Using 2x less memory. Probably faster too, if tested on non-busy server.

    class NumArray {
    int* const m_piSums;
    public:
    NumArray(vector& n) : m_piSums(&n[0]) {
    int s = n.size();
    for (int i = 1; i < s; i++) {
    m_piSums[i] += m_piSums[i-1];
    }
    }
    int sumRange(const int i, const int j) { return m_piSums[j] – (i ? m_piSums[i – 1] : 0); }
    };

    Reply

Leave a Reply