Prefix sum আর difference array

১ · একই যোগফল বারবার — সরল পদ্ধতি কেন ধীর

ধরুন মিরপুরের একটি মুদি দোকানের মালিক রফিক ভাই প্রতিদিনের বিক্রি একটি খাতায় লেখেন। মাসের শেষে তাঁর হিসাবরক্ষক প্রশ্ন করেন: “৩ তারিখ থেকে ১২ তারিখ পর্যন্ত মোট বিক্রি কত?” রফিক ভাই খাতা খুলে দশটি সংখ্যা যোগ করেন। পরের প্রশ্ন: “১০ থেকে ২৫ তারিখ?” আবার ষোলোটি যোগ। তারপর “১ থেকে ২৮?” — আবার প্রায় পুরো মাস। প্রতিটি প্রশ্নে একই সংখ্যাগুলো বারবার যোগ হচ্ছে।

রফিক ভাইয়ের বুদ্ধিমান মেয়ে একটি পরামর্শ দিল: খাতায় আরেকটি কলাম যোগ করুন — “আজ পর্যন্ত মোট বিক্রি”। প্রতিদিন শুধু আগের দিনের মোটের সাথে আজকের বিক্রি যোগ করলেই হয়। এরপর “৩ থেকে ১২ তারিখ” জানতে শুধু দুটি সংখ্যা লাগে: ১২ তারিখ পর্যন্ত মোট থেকে ২ তারিখ পর্যন্ত মোট বাদ দিন। দশটি যোগের বদলে একটি বিয়োগ! bKash-এর স্টেটমেন্টে প্রতিটি লেনদেনের পাশে যে “ব্যালান্স” কলাম থাকে, সেটিও ঠিক এই ধারণা।

এই পর্বের পুরো গল্প এই চলতি যোগফলের কলামকে ঘিরে। প্রথমে সমস্যাটি নিখুঁতভাবে লিখি। আমাদের কাছে n টি সংখ্যার একটি অ্যারে a[0..n−1] আছে (০ থেকে গোনা), আর q টি প্রশ্ন। প্রতিটি প্রশ্ন একটি range query: দুটি index l ও r দেওয়া আছে (0 ≤ l ≤ r < n), বলতে হবে a[l] + a[l + 1] + … + a[r] কত। এই টুকরোটিকে বলে একটি subarray — অ্যারের পাশাপাশি থাকা ঘরগুলোর একটি অবিচ্ছিন্ন অংশ।

Pseudocode (0-based): naive range sum, one query

RANGE-SUM-NAIVE(a, l, r):
    s = 0
    for i = l to r:          // r - l + 1 additions
        s = s + a[i]
    return s

একটি প্রশ্নে কাজ r − l + 1 টি যোগ, সবচেয়ে খারাপ ক্ষেত্রে (l = 0, r = n − 1) n টি। তাই q টি প্রশ্নে মোট সময় O(n·q). কনটেস্টে প্রায়ই n = q = 2 × 10⁵ থাকে — তখন n·q = 4 × 10¹⁰, যা সাধারণ কম্পিউটারে কয়েক মিনিটের কাজ, অথচ সময়সীমা ১–২ সেকেন্ড। প্রশ্ন হলো: প্রতিটি প্রশ্নের আগে একই যোগগুলো আবার কেন করছি?

২ · Prefix sum — একবার বানান, প্রতিটি প্রশ্ন O(1)

অ্যারের শুরু থেকে কোনো জায়গা পর্যন্ত টুকরোকে বলে prefix (উপসর্গ)। prefix sum অ্যারে P-এর প্রতিটি ঘরে রাখা হয় একটি prefix-এর যোগফল। আমরা যে নিয়ম ব্যবহার করব, সেটি মনে গেঁথে নিন:

লক্ষ করুন, P-এর আকার n + 1 — a-এর চেয়ে এক ঘর বেশি। P[0] হলো “শূন্য টি ঘরের যোগফল”, অর্থাৎ 0. এই একটি বাড়তি ঘরই পরে সব off-by-one ঝামেলা দূর করবে। এবার যেকোনো রেঞ্জের যোগফল:

কারণ P[r + 1] হলো a[0] থেকে a[r] পর্যন্ত যোগফল। এর মধ্যে a[0] থেকে a[l − 1] অংশটুকু আমাদের দরকার নেই — আর ঠিক সেটিই P[l]. বড় prefix থেকে ছোট prefix বাদ দিলে মাঝের টুকরোটি থাকে। নিচে a = [3, 1, 4, 1, 5, 9, 2]-এর জন্য P বানানো আর একটি প্রশ্নের উত্তর ধাপে ধাপে দেখুন:

1vector<long long> P(n + 1, 0);   // P[0] = 02for (int i = 0; i < n; ++i)3    P[i + 1] = P[i] + a[i];45// sum(l..r) = P[r+1] - P[l]6long long ans = P[r + 1] - P[l];

শুদ্ধতার প্রমাণ। দাবি: লুপ শেষে সব i-এর জন্য (0 ≤ i ≤ n) P[i] = a[0] + … + a[i − 1]. এটি একটি সরল loop invariant (পর্ব ০৩): “লুপের i-তম ঘূর্ণনের আগে P[0..i] সব ঠিক।” শুরুতে i = 0, আর P[0] = 0 = শূন্য টি ঘরের যোগফল — ঠিক। ঘূর্ণনে P[i + 1] = P[i] + a[i] = (a[0] + … + a[i − 1]) + a[i] — ঠিক, তাই invariant i + 1-এর জন্যও টেকে। লুপ শেষে i = n, তাই সব ঘর ঠিক। এরপর sum(l..r)-এর সূত্রটি শুধু যোগের সাজানো: P[r + 1] = (a[0] + … + a[l − 1]) + (a[l] + … + a[r]) = P[l] + sum(l..r).

Off-by-one — সূচকের নিয়ম একবারে ঠিক করুন

prefix sum-এর সবচেয়ে সাধারণ ভুল সূত্রে নয়, সূচকে। off-by-one ভুল এড়াতে প্রথমেই ঠিক করুন আপনি কোন নিয়ম মানছেন। তিনটি প্রচলিত নিয়ম পাশাপাশি দেখুন:

এর পেছনে একটি গভীর নীতি আছে: রেঞ্জকে half-open interval [l, r + 1) হিসেবে ভাবা — শুরু অন্তর্ভুক্ত, শেষ বাদ। তখন সূত্র দাঁড়ায় “sum[lo, hi) = P[hi] − P[lo]”, দৈর্ঘ্য hi − lo, আর খালি রেঞ্জ মানে lo = hi, যোগফল 0. Edsger Dijkstra ১৯৮২ সালের একটি ছোট নোটে (EWD831, “Why numbering should start at zero”) ঠিক এই কারণেই ০ থেকে গোনা আর half-open রেঞ্জের পক্ষে যুক্তি দেন। C++-এর begin()/end() আর Python-এর range(lo, hi) ও slicing একই নিয়ম মানে।

৩ · 2D prefix sum — আয়তক্ষেত্রের যোগফল চার কোণা থেকে

এবার ধরুন ঢাকার একটি এলাকার মানচিত্র একটি গ্রিডে ভাগ করা — প্রতিটি ঘরে লেখা সেই ব্লকে কয়টি ফার্মেসি আছে। প্রশ্ন আসে: “এই আয়তাকার এলাকায় মোট কয়টি ফার্মেসি?” R × C গ্রিডে একটি আয়তক্ষেত্রে সরলভাবে যোগ করলে প্রতি প্রশ্নে O(R·C) কাজ। 1D-র কৌশলটিকে দুই মাত্রায় নিলে প্রতিটি প্রশ্ন আবার O(1).

2D prefix sum-এ P[i][j] = গ্রিডের ওপরের i টি সারি আর বাঁয়ের j টি কলামের আয়তক্ষেত্রের যোগফল, অর্থাৎ G[0..i−1][0..j−1]. 1D-র মতোই প্রথম সারি আর প্রথম কলাম পুরো শূন্য। একটি ঘর ভরার সূত্র:

কেন বিয়োগ? ওপরের আয়তক্ষেত্র P[i][j + 1] আর বাঁয়ের আয়তক্ষেত্র P[i + 1][j] — দুটিতেই বাঁ-ওপরের কোণার অংশ P[i][j] আছে। যোগ করলে সেটি দুবার গোনা হয়, তাই একবার বাদ দিতে হয়। এই “যোগ করো, দুবার গোনা অংশ বাদ দাও” নীতির নাম inclusion–exclusion. প্রশ্নের উত্তরেও একই নীতি — সারি r1..r2 আর কলাম c1..c2-এর আয়তক্ষেত্র:

বড় আয়তক্ষেত্র থেকে ওপরের পট্টি আর বাঁয়ের পট্টি বাদ দিলাম; কিন্তু বাঁ-ওপরের কোণাটি দুই পট্টিতেই ছিল, তাই দুবার বাদ গেছে — একবার ফেরত যোগ। নিচে 3 × 4 গ্রিডে পুরো P বানানো আর একটি প্রশ্ন দেখুন:

কেন সূত্রটি ঠিক? প্রতিটি ঘর G[x][y] চার কোণার পদে কতবার গোনা হয়, দেখুন। যদি ঘরটি আয়তক্ষেত্রের ভেতরে থাকে, সেটি শুধু P[r2 + 1][c2 + 1]-এ আছে: +1. যদি ঘরটি ওপরের পট্টিতে থাকে (x < r1, কিন্তু কলাম সীমার ভেতরে), সেটি প্রথম আর দ্বিতীয় পদে আছে: +1 − 1 = 0. বাঁ-ওপরের কোণায় (x < r1, y < c1) থাকলে চারটি পদেই: +1 − 1 − 1 + 1 = 0. বাঁয়ের পট্টিতেও একইভাবে 0, আর আয়তক্ষেত্রের ডানে বা নিচে থাকলে কোনো পদেই নেই। তাই ফলাফলে ঠিক ভেতরের ঘরগুলো একবার করে থাকে। এই একই হিসাব-রক্ষার যুক্তি d মাত্রায়ও চলে, তখন 2^d টি কোণা লাগে।

৪ · Prefix sum + hash map — যোগফল k এমন কয়টি subarray

এখন একটি বিখ্যাত ইন্টারভিউ-প্রশ্ন: একটি অ্যারে আর একটি সংখ্যা k দেওয়া আছে। কয়টি subarray-এর যোগফল ঠিক k? অ্যারেতে ঋণাত্মক সংখ্যাও থাকতে পারে — যেমন bKash অ্যাকাউন্টে টাকা ঢোকা (+) আর বের হওয়া (−), আর প্রশ্ন “কয়টি ধারাবাহিক সময়-খণ্ডে নিট পরিবর্তন ঠিক ৩ হাজার টাকা?”

Subarray আছে n(n + 1)/2 টি, তাই সবগুলো যাচাই করা brute force কমপক্ষে Θ(n²). prefix sum দিয়ে প্রশ্নটিকে নতুন ভাষায় লিখি। subarray a[j..i]-এর যোগফল = P[i + 1] − P[j]. তাই

অর্থাৎ প্রতিটি শেষবিন্দু i-এর জন্য প্রশ্ন দাঁড়ায়: “আগের prefix sum-গুলোর (P[0] থেকে P[i]) মধ্যে কয়টির মান ঠিক S − k?”, যেখানে S = P[i + 1] হলো এখন পর্যন্ত চলতি যোগফল। এখন পর্যন্ত দেখা প্রতিটি prefix sum কতবার এসেছে, সেটি একটি hash table-এ (C++-এ unordered_map, Python-এ dict) গুনে রাখলে এই প্রশ্নের উত্তর গড়ে O(1)-এ মেলে। শুরুতে map-এ {0: 1} রাখতে হয় — এটিই P[0] = 0, অর্থাৎ “শুরু থেকেই শুরু” এমন subarray-গুলোর জন্য।

Pseudocode (0-based): count subarrays with sum exactly k

COUNT-SUM-K(a, k):
    seen = map with seen[0] = 1        // the empty prefix P[0] = 0
    S = 0, cnt = 0
    for i = 0 to n - 1:
        S = S + a[i]                   // S = P[i+1]
        cnt = cnt + seen[S - k]        // every earlier P[j] = S - k gives a[j..i]
        seen[S] = seen[S] + 1          // only AFTER counting
    return cnt

নিচে a = [1, 2, −1, 2, 1, −2, 3] আর k = 3-এ পুরো চলা দেখুন। map-এ লেখা আছে “prefix-এর মান : কতবার এসেছে”:

শুদ্ধতার প্রমাণ। প্রতিটি subarray a[j..i] একটি জোড় (j, i + 1)-এর সাথে এক-এক মিলে যায়, যেখানে 0 ≤ j ≤ i. যোগফল k হওয়া মানে P[i + 1] − P[j] = k. লুপের i-তম ধাপে seen[S − k] পড়ার মুহূর্তে map-এ ঠিক P[0], P[1], …, P[i]-এর গণনা আছে — P[i + 1] এখনো ঢোকেনি (ঢোকে পরের লাইনে)। তাই এই ধাপে ঠিক সেই j-গুলো গোনা হয় যাদের জন্য a[j..i]-এর যোগফল k, কোনোটি দুবার নয়, কোনোটি বাদ নয়। সব i-এর ওপর যোগ করলে প্রতিটি উপযুক্ত subarray ঠিক একবার।

Sliding window কেন এখানে চলে না

পর্ব ১৬-এ দেখেছেন, সব সংখ্যা ধনাত্মক হলে sliding window দিয়ে “যোগফল k” জাতীয় প্রশ্ন O(n)-এ হয়: যোগফল কম হলে ডানে বাড়ানো, বেশি হলে বাঁ থেকে ছাঁটা। এর ভিত্তি একটি একমুখিতা (monotonicity): window বড় করলে যোগফল কমে না, ছোট করলে বাড়ে না। ঋণাত্মক সংখ্যা এলেই এই ভিত্তি ভেঙে যায়।

ছোট একটি উদাহরণ: a = [2, −2, 3], k = 3. উত্তর দুটি: a[2..2] = 3 আর a[0..2] = 2 − 2 + 3 = 3. লক্ষ করুন, দুটিরই শেষবিন্দু একই (index 2), কিন্তু শুরু আলাদা। sliding window প্রতিটি শেষবিন্দুর জন্য একটিমাত্র বাঁ সীমা রাখে, তাই দুটির একটি হারাবেই। সব সংখ্যা ধনাত্মক হলে এমন হতে পারে না — তখন P কঠোরভাবে বাড়ে, তাই প্রতিটি শেষবিন্দুর জন্য P[j] = S − k এমন j সর্বোচ্চ একটি। prefix sum + hash map পদ্ধতি এই একমুখিতার ওপর নির্ভর করে না, তাই ঋণাত্মক, শূন্য — সব অবস্থায় ঠিক।

এবার কোডে — প্রথমে range-sum প্রশ্ন, তারপর sum = k গণনা, আর ছোট ইনপুটে একটি brute force দিয়ে নিজের উত্তর মিলিয়ে নেওয়া:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <utility>
#include <initializer_list>
using namespace std;

int main() {
    vector<long long> a = {3, 1, 4, 1, 5, 9, 2};
    int n = (int)a.size();
    vector<long long> P(n + 1, 0);                       // P[0] = 0
    for (int i = 0; i < n; ++i) P[i + 1] = P[i] + a[i];
    cout << "P =";
    for (long long x : P) cout << ' ' << x;
    cout << '\n';
    for (auto [l, r] : {pair{2, 5}, pair{0, 6}, pair{4, 4}})
        cout << "sum(" << l << ".." << r << ") = " << P[r + 1] - P[l] << '\n';

    vector<long long> b = {1, 2, -1, 2, 1, -2, 3};
    long long k = 3, s = 0, cnt = 0;
    unordered_map<long long, long long> seen{{0, 1}};     // the empty prefix
    for (long long x : b) {
        s += x;
        if (auto it = seen.find(s - k); it != seen.end()) cnt += it->second;
        ++seen[s];                                          // after counting
    }
    long long brute = 0;                                    // O(n^2) check
    for (int i = 0; i < (int)b.size(); ++i)
        for (long long t = 0, j = i; j < (int)b.size(); ++j)
            if ((t += b[j]) == k) ++brute;
    cout << "subarrays with sum " << k << ": " << cnt << " (brute force: " << brute << ")\n";
}

P = 0 3 4 8 9 14 23 25
sum(2..5) = 19
sum(0..6) = 25
sum(4..4) = 5
subarrays with sum 3: 6 (brute force: 6)

a = [3, 1, 4, 1, 5, 9, 2]
P = [0]                                   # P[0] = 0
for x in a:
    P.append(P[-1] + x)                   # P[i+1] = P[i] + a[i]
print("P =", *P)
for l, r in [(2, 5), (0, 6), (4, 4)]:
    print(f"sum({l}..{r}) = {P[r + 1] - P[l]}")

b = [1, 2, -1, 2, 1, -2, 3]
k, s, cnt = 3, 0, 0
seen = {0: 1}                             # the empty prefix
for x in b:
    s += x
    cnt += seen.get(s - k, 0)
    seen[s] = seen.get(s, 0) + 1          # after counting
brute = sum(1 for i in range(len(b)) for j in range(i, len(b))
            if sum(b[i:j + 1]) == k)      # slow check, fine for tiny input
print(f"subarrays with sum {k}: {cnt} (brute force: {brute})")

P = 0 3 4 8 9 14 23 25
sum(2..5) = 19
sum(0..6) = 25
sum(4..4) = 5
subarrays with sum 3: 6 (brute force: 6)

৫ · একই ছাঁচে আরও তিন কৌশল — শূন্য-যোগফল, prefix XOR, prefix count

“চলতি মান রাখো, দুটি prefix-এর পার্থক্য দিয়ে রেঞ্জ বের করো” — এই ছাঁচ যোগফলের বাইরেও বহু জায়গায় খাটে। তিনটি সবচেয়ে কাজের রূপ দেখি।

শূন্য যোগফলের দীর্ঘতম subarray

a[j..i]-এর যোগফল 0 মানে P[i + 1] = P[j] — দুটি prefix sum সমান। দীর্ঘতম চাই, তাই প্রতিটি মানের প্রথম উপস্থিতির সূচক map-এ রাখুন (পরে এলে আর বদলাবেন না)। একই মান আবার এলে দৈর্ঘ্য = বর্তমান সূচক − প্রথম সূচক। উদাহরণ a = [3, 4, −7, 1, 3, 3, 1, −4]:

দীর্ঘতম 4: P[2] = P[6] = 7, তাই a[2..5] = −7 + 1 + 3 + 3 = 0. সময় গড়ে O(n), জায়গা O(n). একই কৌশলে একটি জনপ্রিয় প্রশ্নও হয়ে যায়: “০ আর ১ সমান সংখ্যায় আছে এমন দীর্ঘতম subarray” — প্রতিটি 0-কে −1 ধরলেই সেটি শূন্য-যোগফলের প্রশ্ন (অনুশীলন ৪)। আর “যোগফল ঠিক k এমন দীর্ঘতম” চাইলে S − k-এর প্রথম উপস্থিতি খুঁজুন।

Prefix XOR

XOR (⊕, C++ ও Python-এ ^)-এর একটি বিশেষ গুণ আছে: x ⊕ x = 0, আর x ⊕ 0 = x. অর্থাৎ XOR নিজেই নিজের উল্টো — বিয়োগের কাজও XOR দিয়ে হয়। তাই prefix XOR X[0] = 0, X[i + 1] = X[i] ⊕ a[i] রাখলে:

কারণ X[r + 1]-এ a[0..r] আছে, X[l]-এ a[0..l−1]; দুটি XOR করলে a[0..l−1] অংশ দুবার এসে নিজেকে বাতিল করে। “XOR ঠিক k এমন কয়টি subarray?” প্রশ্নেও অংশ ৪-এর পদ্ধতি হুবহু চলে — শুধু S − k-এর বদলে S ^ k খুঁজুন, কারণ X[j] ⊕ S = k ⇔ X[j] = S ⊕ k.

Prefix count — একটি রেঞ্জে কোনো মান কতবার

ধরুন একটি এলাকার ৩০ দিনের রেকর্ড: প্রতিদিন লোডশেডিং হয়েছে কি না। প্রশ্ন: “১০ থেকে ২০ তারিখের মধ্যে কত দিন লোডশেডিং?” প্রতিটি দিনকে 1 (হয়েছে) বা 0 (হয়নি) ধরলে এটি সাধারণ prefix sum: cnt[i + 1] = cnt[i] + (দিন i-এ লোডশেডিং ? 1 : 0). একই ধারণা যেকোনো শর্তে চলে — একটি string-এর s[l..r]-এ কয়টি স্বরবর্ণ, একটি পরীক্ষার ফলের তালিকায় একটি রোল-রেঞ্জে কতজন A+.

একাধিক মানের জন্য একসাথে চাইলে প্রতিটি মানের নিজের prefix count রাখুন: ছোট হাতের ২৬টি ইংরেজি অক্ষরের জন্য cnt[c][i] — জায়গা O(26·n), প্রতি প্রশ্ন O(1). “s[l..r]-এর অক্ষরগুলো সাজিয়ে palindrome বানানো যায় কি না?” জাতীয় প্রশ্নে এটি খুব কাজের: ২৬টি গণনা O(26)-এ বের করে দেখুন বিজোড় গণনা কয়টি। তবে মানের সংখ্যা (alphabet) বড় হলে এই জায়গা অসম্ভব হয়ে যায় — তখন অন্য কৌশল লাগে, যেমন পর্ব ৩৭-এর Mo’s algorithm.

৬ · Difference array — অনেকগুলো রেঞ্জ আপডেট, শেষে একবার হিসাব

এবার উল্টো সমস্যা। মিরপুর থেকে মতিঝিল পর্যন্ত রাস্তাকে ৮টি অংশে ভাগ করা হয়েছে (অংশ 0 থেকে 7). ট্রাফিক বিভাগের কাছে বাস রুটের তালিকা: “২টি বাস অংশ 1 থেকে 4 পর্যন্ত চলে”, “৩টি বাস অংশ 3 থেকে 6”, এমন অনেকগুলো। শেষে জানতে চাই প্রতিটি অংশে মোট কয়টি বাস — কোথায় জ্যাম সবচেয়ে বেশি হবে। একইভাবে একটি স্কুলে বিভিন্ন শাখার ছাত্রদের জন্য বেঞ্চ বরাদ্দ, বা একটি হলের আসন-সারিতে বুকিং — সব জায়গায় প্রশ্ন একই: অনেকগুলো “[l, r]-এর সব ঘরে v যোগ করো”, তারপর সব ঘরের মান।

সরলভাবে প্রতিটি range update-এ r − l + 1 টি ঘরে যোগ: q টি আপডেটে O(n·q). কিন্তু একটি পর্যবেক্ষণ সব বদলে দেয়। চূড়ান্ত অ্যারে A-এর পাশাপাশি দুটি ঘরের পার্থক্য দেখুন: D[i] = A[i] − A[i − 1] (D[0] = A[0]). “[l, r]-এ v যোগ” করলে কোন পার্থক্যগুলো বদলায়? রেঞ্জের ভেতরে পাশাপাশি দুটি ঘর দুটিই v বেড়েছে, তাই তাদের পার্থক্য একই। বদলায় শুধু দুটি সীমানা: l-এ ঢোকার মুহূর্তে মান v লাফ দেয় (D[l] += v), আর r পেরিয়ে বেরোনোর মুহূর্তে v নামে (D[r + 1] −= v). এই D-কে বলে difference array, আর A হলো D-এর prefix sum — prefix sum-এর ঠিক উল্টো কাজ।

Pseudocode (0-based): q range updates, then read every value

RANGE-ADD-ALL(n, updates):
    D = array of n + 1 zeros            // one extra cell for r + 1 = n
    for each (l, r, v) in updates:      // O(1) per update
        D[l] = D[l] + v
        D[r + 1] = D[r + 1] - v
    run = 0
    for i = 0 to n - 1:                 // one prefix pass, O(n)
        run = run + D[i]
        A[i] = run
    return A

রাস্তার উদাহরণে চারটি রুট: +2 অংশ [1, 4]-এ, +3 অংশ [3, 6]-এ, +1 অংশ [0, 2]-এ, আর +1 অংশ [5, 7]-এ। প্রতিটি আপডেটে D-তে শুধু দুটি ঘর বদলায় — দেখুন:

শুদ্ধতার প্রমাণ। একটি আপডেট (l, r, v) D-তে যা করে, তার প্রভাব prefix sum A[i] = D[0] + … + D[i]-এ দেখি। i < l হলে দুটি বদলানো ঘরের কোনোটিই যোগে আসে না: প্রভাব 0. l ≤ i ≤ r হলে শুধু D[l]-এর +v আসে: প্রভাব v. i > r হলে দুটিই আসে: v − v = 0. অর্থাৎ ঠিক [l, r]-এর ঘরগুলোতে v যোগ হয়। আর যোগ রৈখিক (linear) — একাধিক আপডেটের প্রভাব আলাদা আলাদা যোগ হয়, কোনো ক্রমের ওপর নির্ভর করে না। তাই সব আপডেট শেষে একটি prefix pass-এ সবার মিলিত ফল।

কোডে — চারটি রুট আর সবচেয়ে ব্যস্ত অংশ:

#include <iostream>
#include <vector>
#include <tuple>
#include <initializer_list>
using namespace std;

int main() {
    int n = 8;                                     // road segments 0..7
    vector<long long> D(n + 1, 0);                 // one extra cell
    for (auto [l, r, v] : {tuple{1, 4, 2}, tuple{3, 6, 3}, tuple{0, 2, 1}, tuple{5, 7, 1}}) {
        D[l] += v;                                 // start adding v at l
        D[r + 1] -= v;                             // stop after r
    }
    cout << "D =";
    for (long long x : D) cout << ' ' << x;
    cout << '\n';
    vector<long long> bus(n);
    long long run = 0;
    for (int i = 0; i < n; ++i) bus[i] = run += D[i];   // one prefix pass
    cout << "buses =";
    for (long long x : bus) cout << ' ' << x;
    cout << '\n';
    int best = 0;
    for (int i = 1; i < n; ++i) if (bus[i] > bus[best]) best = i;
    cout << "busiest segment: " << best << " (" << bus[best] << " buses)\n";
}

D = 1 2 0 2 0 -1 0 -3 -1
buses = 1 3 3 5 5 4 4 1
busiest segment: 3 (5 buses)

n = 8                                     # road segments 0..7
D = [0] * (n + 1)                         # one extra cell
for l, r, v in [(1, 4, 2), (3, 6, 3), (0, 2, 1), (5, 7, 1)]:
    D[l] += v                             # start adding v at l
    D[r + 1] -= v                         # stop after r
print("D =", *D)
bus, run = [], 0
for i in range(n):
    run += D[i]                           # one prefix pass
    bus.append(run)
print("buses =", *bus)
best = max(range(n), key=lambda i: bus[i])   # first index of the maximum
print(f"busiest segment: {best} ({bus[best]} buses)")

D = 1 2 0 2 0 -1 0 -3 -1
buses = 1 3 3 5 5 4 4 1
busiest segment: 3 (5 buses)

2D difference array — আয়তক্ষেত্রে আপডেট

গ্রিডে “সারি r1..r2, কলাম c1..c2-এর সব ঘরে v যোগ” — 2D prefix sum-এর উল্টো কাজ। চারটি কোণায় চিহ্ন দিন, তারপর শেষে একবার 2D prefix sum নিন:

Pseudocode (0-based): add v to rectangle (r1..r2, c1..c2); D is (R+1) x (C+1)

D[r1][c1]         += v
D[r1][c2 + 1]     -= v
D[r2 + 1][c1]     -= v
D[r2 + 1][c2 + 1] += v       // added back: it was subtracted twice
// after all updates: A = 2D prefix sum of D  (section 3), O(R*C) once

প্রতিটি আপডেট O(1), শেষে Θ(R·C). চিহ্নের ছক (+, −, −, +) 2D প্রশ্নের সূত্রের মতোই — একই inclusion–exclusion. বাস্তব উদাহরণ: একটি মানচিত্রে অনেকগুলো মোবাইল টাওয়ারের আয়তাকার কভারেজ এলাকা দেওয়া, জানতে হবে প্রতিটি ব্লক কতগুলো টাওয়ারের আওতায়। কনটেস্টে “অনেকগুলো আয়তক্ষেত্র আঁকা হলো, কতগুলো ঘর ঠিক k টি আয়তক্ষেত্রে ঢাকা” জাতীয় সমস্যা এভাবেই হয়।

৭ · সীমা — মান বদলালে কী হয়, আর overflow

Point update prefix sum ভেঙে দেয়

prefix sum-এর সব জাদু একটি শর্তে দাঁড়িয়ে: অ্যারে বদলায় না (static). এখন ধরুন প্রশ্নের মাঝে মাঝে আসে “a[i]-এর মান বদলে x করো” — একটি point update. তখন P[i + 1], P[i + 2], …, P[n] সবগুলো বদলে যায়, কারণ সবগুলোতেই a[i] আছে। সবচেয়ে খারাপ ক্ষেত্রে (i = 0) n টি ঘর ঠিক করতে হয়: আপডেট O(n). difference array-র সমস্যা উল্টো দিকে: আপডেট O(1), কিন্তু মাঝপথে একটি মান পড়তে পুরো prefix pass, O(n).

একটি কাজের নিয়ম: সমস্যা পড়ে প্রথমেই জিজ্ঞেস করুন “আপডেট আর প্রশ্ন কি মিশে আসে?” না হলে prefix sum বা difference array — সবচেয়ে সরল, সবচেয়ে দ্রুত, ভুলের সুযোগ সবচেয়ে কম। মিশে এলে log n-এর কাঠামো লাগবে, যা মডিউল ৫-এ আসছে। সব আপডেট আর প্রশ্ন আগে থেকে জানা থাকলে কখনো কখনো এগুলোকে সাজিয়ে নিয়ে (offline) আবার সরল কৌশলেই কাজ সারা যায়।

Overflow — যোগফল সংখ্যার চেয়ে অনেক বড়

C++-এ int সাধারণত 32 bit, সর্বোচ্চ মান 2,147,483,647 (প্রায় 2.1 × 10⁹). কনটেস্টে প্রায়ই n ≤ 2 × 10⁵ আর প্রতিটি |a[i]| ≤ 10⁹. প্রতিটি সংখ্যা int-এ ধরে, কিন্তু prefix sum পৌঁছাতে পারে 2 × 10¹⁴-এ — int-এর চেয়ে প্রায় এক লাখ গুণ বড়। signed int-এর integer overflow C++-এ undefined behaviour: সাধারণত মান ঘুরে ঋণাত্মক হয়ে যায়, কোনো error ছাড়া।

৮ · AI-এর যুগে prefix sum — সূত্র সহজ, সূচক কঠিন

“Subarray sum equals k সমাধান করো” লিখলে যেকোনো AI কয়েক সেকেন্ডে কোড দেয়, আর বেশিরভাগ সময় সেটি ঠিক — কারণ সমস্যাটি অত্যন্ত পরিচিত। বিপদ শুরু হয় যখন সমস্যা একটু বদলায়: ১-ভিত্তিক ইনপুট, “দীর্ঘতম” বনাম “কয়টি”, k = 0, 2D, বা মাঝে আপডেট। AI তখন প্রায়ই পরিচিত সমাধানটি সামান্য বদলে দেয় — সূচক এক ঘর সরে যায়, map-এর লাইনের ক্রম উল্টে যায়, বা টাইপ int থেকে যায়। কোড চলে, ছোট উদাহরণে ঠিক উত্তরও দেয়, তারপর লুকানো test-এ “Wrong Answer”.

Prefix sum-এ AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) prefix sum কোড যাচাইয়ের চেকলিস্ট

• সূচক-নিয়ম এক বাক্যে লিখেছি (P[i] মানে কোন ঘরগুলোর যোগফল), আর পুরো কোডে সেটিই মানা হয়েছে
• l = 0, l = r আর l = 0, r = n − 1 — তিনটি প্রশ্ন হাতে dry run করে মিলিয়েছি
• hash-এর পদ্ধতিতে {0: 1} আছে আর গণনা আপডেটের আগে হয় — k = 0 দিয়ে পরীক্ষা করেছি
• ঋণাত্মক সংখ্যা থাকলে sliding window ব্যবহার করা হয়নি
• যোগফল আর গণনা long long-এ; সবচেয়ে বড় সম্ভাব্য যোগফল হিসাব করে দেখেছি
• ছোট random ইনপুটে brute force-এর সাথে কয়েকশো বার মিলিয়ে stress test করেছি