Mean of Range in Array Using Prefix Sum

Introduction

When working with arrays, one common problem is calculating the mean (average) of elements within a given range. If we process multiple queries on the same array, a naive approach can become inefficient.

In this article, we’ll explore how to efficiently compute the mean of subarray ranges using the Prefix Sum technique, reducing time complexity significantly.

Problem Statement

Given:

• An integer array arr[]

• A 2D array queries[][], where each query contains two indices [l, r]

For each query:

• Extract the subarray from index l to r (inclusive)

• Compute the mean (average) of the elements

• Return the floor value of the mean

Example

Input:

• arr = [1, 2, 3, 4, 5]

• queries = [[0, 2], [1, 3], [0, 4]]

Output:

• [2, 3, 3]

Explanation:

• Query [0,2] → [1,2,3] → sum = 6 → mean = 2

• Query [1,3] → [2,3,4] → sum = 9 → mean = 3

• Query [0,4] → [1,2,3,4,5] → sum = 15 → mean = 3

Naive Approach (Inefficient)

For each query:

• Loop from l to r

• Calculate sum

Time Complexity: O(n × q)

This is too slow for large inputs.

Optimized Approach: Prefix Sum

What is Prefix Sum?

A prefix sum array stores cumulative sums:

prefix[i] = arr[0] + arr[1] + ... + arr[i]

Example:

• arr = [1, 2, 3, 4, 5]

• prefix = [1, 3, 6, 10, 15]

How It Works

Step 1: Build Prefix Sum Array

prefix[i] = prefix[i-1] + arr[i]

Step 2: Calculate Range Sum

If l == 0:

sum = prefix[r]

Else:

sum = prefix[r] - prefix[l - 1]

Step 3: Compute Mean

mean = sum / (r - l + 1)

(Note: Integer division automatically gives the floor value in C#)

C# Implementation

using System;
using System.Collections.Generic;

public class Solution
{
    public List<int> FindMean(int[] arr, int[][] queries)
    {
        int n = arr.Length;
        List<int> result = new List<int>();

        // Step 1: Build prefix sum array
        int[] prefix = new int[n];
        prefix[0] = arr[0];

        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] + arr[i];
        }

        // Step 2: Process queries
        foreach (var q in queries)
        {
            int l = q[0];
            int r = q[1];
            int sum;

            if (l == 0)
            {
                sum = prefix[r];
            }
            else
            {
                sum = prefix[r] - prefix[l - 1];
            }

            int count = r - l + 1;
            int mean = sum / count; // floor value

            result.Add(mean);
        }

        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n + q)

• Space Complexity: O(n)

Why Use Prefix Sum?

• Reduces repeated calculations

• Efficient for large datasets

• Commonly used in real-world applications like analytics and reporting

Conclusion

Using the Prefix Sum technique, we can efficiently solve range-based problems like finding the mean of subarrays. This approach is simple, fast, and highly scalable.

If you’re preparing for coding interviews or working on performance-critical applications, mastering this technique is essential.