[FEATURE]: Add Basic Prefix Sum Algorithm with Tests

[ShubhamG2004]

Motivation

Overview

Add a basic Prefix Sum algorithm in the PrefixSum/ folder, along with unit tests.

Contents

• BasicPrefixSum.js: Implementation of prefix sum for an array of numbers.
  • Validates input (must be a numeric array) and throws TypeError for invalid inputs.
• BasicPrefixSum.test.js: Vitest test suite covering:
  1. Correct prefix sum computation on a normal array.
  2. Handling of empty array input.
  3. Error thrown when input is not a numeric array.

Goal

• Add a reusable prefix sum utility.
• Ensure code quality by covering edge and error cases via tests.

Folder Structure

PrefixSum/
├── BasicPrefixSum.js
└── BasicPrefixSum.test.js

Examples

Prefix Sum is a precomputation technique used to answer range sum queries in constant time.
It transforms repeated O(n) sum queries into O(1) using:

prefix[j] - prefix[i - 1]

Useful in:

• Range Sum Queries
• Subarray problems
• Competitive programming & interviews

Possible workarounds

No response

Additional information

While Prefix Sum is efficient for range sum queries, if you cannot precompute the array (e.g., in streaming data or memory-constrained environments), here are some alternatives:

Brute-force summation:

Recalculate the sum for each query using a loop.
- Time: O(n) per query
- Simple, but inefficient for large datasets or frequent queries.

Segment Tree or Binary Indexed Tree (Fenwick Tree):

Suitable for dynamic updates and range queries.

• Time: O(log n) for both updates and queries
• More complex to implement than prefix sum.

Memoization:
Cache previously computed range sums if the array is immutable and queries are repeated.