← Back to DSA Course | Chapter 2: Arrays | Lesson 6 of 8

Prefix Sum क्या है

एक prefix sum एक scoreboard पर running score रखने जैसा है। एक बार आपके पास यह हो, किसी भी stretch का total ढूंढना बस एक quick subtraction है।

In this page:

  1. Prefix Sum Idea
  2. Range Sum
  3. Difference of Prefix Values
  4. Prefix Sum Applications
  5. Prefix Sum Practice
Syntax
markup 
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix[i + 1] = prefix[i] + arr[i]

range_sum = prefix[r + 1] - prefix[l]   # sum of arr[l..r]

Prefix Sum Idea

एक prefix sum array हर index i पर, शुरुआत से i तक के सभी elements का running total store करता है। इसे एक बार O(n) में बनाना बाद में कई range-sum queries का जवाब देना लगभग instant बना देता है, हर बार elements फिर से जोड़ने के बजाय।

उदाहरण: Prefix Sum Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 4, 6, 8};
    int n = 4;
    int prefix[4];
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i]; // running total
    cout << "prefix[2]: " << prefix[2] << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8};
        int[] prefix = new int[4];
        prefix[0] = arr[0];
        for (int i = 1; i < 4; i++) prefix[i] = prefix[i - 1] + arr[i];
        System.out.println("prefix[2]: " + prefix[2]);
    }
}
arr = [2, 4, 6, 8]
prefix = [arr[0]]
for x in arr[1:]:
    prefix.append(prefix[-1] + x)  # running total
print("prefix[2]:", prefix[2])
#include <stdio.h>
int main() {
    int arr[] = {2, 4, 6, 8};
    int prefix[4];
    prefix[0] = arr[0];
    for (int i = 1; i < 4; i++) prefix[i] = prefix[i - 1] + arr[i];
    printf("prefix[2]: %d\n", prefix[2]);
    return 0;
}

Range Sum

Index l से r तक elements का sum पाने के लिए, आपको इन्हें एक-एक करके जोड़ने की ज़रूरत नहीं: l से ठीक पहले prefix sum को r पर prefix sum से subtract करें, जो एक O(n) sum को एक O(1) lookup में बदल देता है।

उदाहरण: Range Sum

#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = 5;
    int prefix[5];
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i];
    int l = 1, r = 3;
    int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0); // O(1) lookup
    cout << "Sum from " << l << " to " << r << ": " << rangeSum << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 4, 6, 8, 10};
        int[] prefix = new int[5];
        prefix[0] = arr[0];
        for (int i = 1; i < 5; i++) prefix[i] = prefix[i - 1] + arr[i];
        int l = 1, r = 3;
        int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0);
        System.out.println("Sum from " + l + " to " + r + ": " + rangeSum);
    }
}
arr = [2, 4, 6, 8, 10]
prefix = [arr[0]]
for x in arr[1:]:
    prefix.append(prefix[-1] + x)
l, r = 1, 3
range_sum = prefix[r] - (prefix[l - 1] if l > 0 else 0)  # O(1) lookup
print(f"Sum from {l} to {r}:", range_sum)
#include <stdio.h>
int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int prefix[5];
    prefix[0] = arr[0];
    for (int i = 1; i < 5; i++) prefix[i] = prefix[i - 1] + arr[i];
    int l = 1, r = 3;
    int rangeSum = prefix[r] - (l > 0 ? prefix[l - 1] : 0);
    printf("Sum from %d to %d: %d\n", l, r, rangeSum);
    return 0;
}

Difference of Prefix Values

वह subtraction trick, prefix[r] − prefix[l−1], prefix sums के पीछे का पूरा idea है: किसी भी contiguous range का total सीधे range scan करने के बजाय सिर्फ दो precomputed values से recover किया जा सकता है।

उदाहरण: Difference of Prefix Values

#include <iostream>
using namespace std;
int main() {
    int prefix[] = {2, 6, 12, 20, 30};
    int l = 2, r = 4;
    // prefix[r] - prefix[l-1] recovers the range total from two lookups.
    int total = prefix[r] - prefix[l - 1];
    cout << "Range total: " << total << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] prefix = {2, 6, 12, 20, 30};
        int l = 2, r = 4;
        int total = prefix[r] - prefix[l - 1];
        System.out.println("Range total: " + total);
    }
}
prefix = [2, 6, 12, 20, 30]
l, r = 2, 4
# prefix[r] - prefix[l-1] recovers the range total from two lookups.
total = prefix[r] - prefix[l - 1]
print("Range total:", total)
#include <stdio.h>
int main() {
    int prefix[] = {2, 6, 12, 20, 30};
    int l = 2, r = 4;
    int total = prefix[r] - prefix[l - 1];
    printf("Range total: %d\n", total);
    return 0;
}

Prefix Sum Applications

Simple sums से आगे, वही technique यह count करने तक extend होती है कि एक range में कितनी values एक condition पूरी करती हैं, या यह compare करना कि दो ranges का total बराबर है या नहीं, data के किसी appropriately transformed version पर एक prefix array बनाकर।

उदाहरण: Prefix Sum Applications

#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 0, 1, 1, 0, 1};
    int n = 6;
    int prefixOnes[6];
    prefixOnes[0] = arr[0];
    for (int i = 1; i < n; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i]; // count of 1s so far
    cout << "Count of 1s in [0..3]: " << prefixOnes[3] << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 0, 1, 1, 0, 1};
        int[] prefixOnes = new int[6];
        prefixOnes[0] = arr[0];
        for (int i = 1; i < 6; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i];
        System.out.println("Count of 1s in [0..3]: " + prefixOnes[3]);
    }
}
arr = [1, 0, 1, 1, 0, 1]
prefix_ones = [arr[0]]
for x in arr[1:]:
    prefix_ones.append(prefix_ones[-1] + x)  # count of 1s so far
print("Count of 1s in [0..3]:", prefix_ones[3])
#include <stdio.h>
int main() {
    int arr[] = {1, 0, 1, 1, 0, 1};
    int prefixOnes[6];
    prefixOnes[0] = arr[0];
    for (int i = 1; i < 6; i++) prefixOnes[i] = prefixOnes[i - 1] + arr[i];
    printf("Count of 1s in [0..3]: %d\n", prefixOnes[3]);
    return 0;
}

Prefix Sum Practice

Prefix sums बनाना सस्ता है और इनाम तब बहुत ज़्यादा मिलता है जब आपको उसी static array पर कई range queries का जवाब देना हो, एक one-time O(n) setup के बाद एक O(n) per-query cost को O(1) में बदलते हुए।

उदाहरण: Prefix Sum Practice

#include <iostream>
using namespace std;
int main() {
    // One-time O(n) build, then every range query answered in O(1).
    int arr[] = {3, 1, 4, 1, 5, 9};
    int n = 6;
    int prefix[6];
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + arr[i];
    cout << "Query [1,4]: " << prefix[4] - prefix[0] << endl;
    cout << "Query [0,5]: " << prefix[5] << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9};
        int[] prefix = new int[6];
        prefix[0] = arr[0];
        for (int i = 1; i < 6; i++) prefix[i] = prefix[i - 1] + arr[i];
        System.out.println("Query [1,4]: " + (prefix[4] - prefix[0]));
        System.out.println("Query [0,5]: " + prefix[5]);
    }
}
arr = [3, 1, 4, 1, 5, 9]
prefix = [arr[0]]
for x in arr[1:]:
    prefix.append(prefix[-1] + x)
print("Query [1,4]:", prefix[4] - prefix[0])
print("Query [0,5]:", prefix[5])
#include <stdio.h>
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9};
    int prefix[6];
    prefix[0] = arr[0];
    for (int i = 1; i < 6; i++) prefix[i] = prefix[i - 1] + arr[i];
    printf("Query [1,4]: %d\n", prefix[4] - prefix[0]);
    printf("Query [0,5]: %d\n", prefix[5]);
    return 0;
}
Related Topics

Two Sum समस्या · Two Pointer तकनीक · Kadane का Algorithm · Sliding Window तकनीक

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. एक inclusive range के लिए prefix[r] - prefix[l - 1] के बजाय prefix[r] - prefix[l] उपयोग करना, जो arr[l] छोड़ देता है।
  2. l == 0 होने पर prefix[l - 1] access करना, जो bounds से बाहर है जब तक आप एक extra leading zero उपयोग न करें।
  3. हर query के लिए एक loop से sum recompute करना, जो एक बार prefix array बनाने के purpose को हरा देता है।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Two Pointer Technique Next Lesson → Kadanes Algorithm

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.