072 — 2D Prefix Sum

এতক্ষণ এক সারিতে ফিতা কাটছিলে (068)। এবার সেই idea দুই দিকে ছড়াবে — একটা matrix-এ যেকোনো rectangle-এর sum এক নিমেষে। নতুন জিনিস একটাই: চারটা term-এর formula, যেটা আসলে Level 3-এর inclusion-exclusion-এর geometry রূপ। কোণার ব্লক দুবার কাটা পড়ে, একবার ফেরত — এই ছবিটা আঁকতে পারলেই formula মুখস্থ করতে হবে না।

Source

• Original source: Classic technique (2D prefix sum, inclusion-exclusion)
• Platform: LeetCode Range Sum Query 2D Immutable — https://leetcode.com/problems/range-sum-query-2d-immutable/, CSES Forest Queries — https://cses.fi/problemset/task/1652
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: 2D prefix sum (rectangle sum via inclusion-exclusion)
• Basic idea inherited from: 067 — Prefix Sum (এবং Level 3-এর 044 — inclusion-exclusion)

1. Problem in simple words

একটা 2D matrix mat (R সারি × C কলাম) দেওয়া। অনেকগুলো query আসবে, প্রতিটায় চারটা সংখ্যা: (r1, c1) (উপরের-বাঁ কোণ) আর (r2, c2) (নিচের-ডান কোণ)। তোমাকে বলতে হবে ওই rectangle-এর ভেতরের সব cell-এর মোট sum কত (চার প্রান্ত সহ)।

মুশকিল: query অনেক, rectangle বড় হতে পারে। প্রতিবার পুরো rectangle ঘুরে যোগ করলে ধীর। তাই আগে একবার 2D prefix sum বানিয়ে নিয়ে, প্রতিটা query O(1)-এ দিতে হবে।

2. What is the math idea?

মূল idea হলো 2D prefix sum + inclusion-exclusion।

P[i][j] = উপরের-বাঁ কোণ (0,0) থেকে (i-1, j-1) পর্যন্ত পুরো rectangle-এর মোট। Build:

P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]

(উপরের পট্টি + বাঁয়ের পট্টি, কিন্তু কোণা দুবার গোনা হলো, তাই একবার বিয়োগ।)

আর rectangle (r1,c1)..(r2,c2)-এর sum:

sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

বড় rectangle থেকে উপরের পট্টি বাদ, বাঁয়ের পট্টি বাদ — কিন্তু উপরের-বাঁ কোণার ব্লক দুবার বাদ পড়ল, একবার ফেরত যোগ। এটাই inclusion-exclusion।

3. Which basic idea does this inherit from?

দুই জায়গা থেকে: 067 (Prefix Sum)-এর "জমা যোগফল" idea, আর Level 3-এর 044 (inclusion-exclusion)-এর "বেশি কাটলে ফেরত দাও" নীতি।

067-এ এক dimension-এ sum = P[r+1] - P[l] ছিল — দুটো term। দুই dimension-এ overlap তৈরি হয়, তাই চারটা term লাগে: যোগ-বিয়োগের নাচ যাতে প্রতিটা cell ঠিক একবার গোনা হয়। সেই "দুবার গোনা হলে একবার বিয়োগ" হলো Level 3-এর Venn-চিন্তারই geometry version। দুটো idea একসাথে না বুঝলে এই formula মুখস্থ-নির্ভর হয়ে পড়বে।

4. Real-life analogy

ভাবো একটা শহরের মানচিত্রে জমির দাম বসানো গ্রিডে। তুমি একটা আয়তাকার এলাকার মোট দাম জানতে চাও।

তোমার কাছে আছে একটা সুবিধাজনক tool: প্রতিটা কোণের জন্য "শহরের একদম উপরের-বাঁ কোণ থেকে এই বিন্দু পর্যন্ত পুরো আয়তক্ষেত্রের মোট দাম" আগে থেকে লেখা।

মাঝের একটা rectangle-এর দাম পেতে: বড় রেকটাঙ্গল (নিচের-ডান কোণ পর্যন্ত) নাও, তার থেকে উপরের অংশ বাদ দাও, বাঁয়ের অংশ বাদ দাও। কিন্তু উপরের-বাঁ কোণার টুকরোটা দুবার বাদ পড়ল (একবার "উপরের"-এ, একবার "বাঁয়ের"-এ), তাই সেটা একবার ফেরত যোগ করো। চারটা সংখ্যা দিয়ে যেকোনো rectangle।

5. Visual explanation

mat = [[3,1,4],[2,5,6],[1,0,2]]। build করলে P (size 4×4, প্রথম সারি/কলাম sentinel 0):

mat:            P (2D prefix):
 3  1  4        0   0   0   0
 2  5  6        0   3   4   8
 1  0  2        0   5  11  21
                0   6  12  24

P[i][j] = (0,0) থেকে (i-1,j-1) পর্যন্ত মোট।
যেমন P[2][2] = 11 = 3+1+2+5 (উপরের-বাঁ 2×2 ব্লক)।

এবার rectangle (1,1)..(2,2) চাই — মান 5,6,0,2, মোট 13। inclusion-exclusion-এর ছবি:

   c1=1   c2=2
   ┌───────────────┐
   │   B (উপরের)   │ r1=1  ← বাদ দিতে হবে
   ├───────┬───────┤
   │   C   │   ★   │ r2=2  ★ = আসল চাই (5,6,0,2)
   │(বাঁয়ের)│       │
   └───────┴───────┘

sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
    = P[3][3]       - P[1][3]     - P[3][1]     + P[1][1]
    = 24            - 8           - 6           + 3
    = 13                                            (5+6+0+2 = 13 ✓)

মূল কথা: বড়টা (24) থেকে উপরের পট্টি (8) আর বাঁয়ের পট্টি (6) বাদ। কিন্তু উপরের-বাঁ কোণ (P[1][1]=3) দুবার বাদ পড়েছে, তাই একবার (+3) ফেরত। চার term-এর নাচ।

6. Example input and output

mat = [[3, 1, 4],
       [2, 5, 6],
       [1, 0, 2]]

query (r1,c1,r2,c2) -> sum    কোন cell গুলো
-----------------------------------------------------
(0, 0, 2, 2)        -> 24     পুরো matrix
(1, 1, 2, 2)        -> 13     5,6,0,2
(0, 0, 0, 0)        -> 3      একটাই cell (top-left)
(1, 1, 1, 1)        -> 5      একটাই cell (মাঝখানে)
(0, 1, 1, 2)        -> 16     1,4,5,6
(2, 0, 2, 2)        -> 3      নিচের পুরো সারি 1,0,2

Edge case: r1=r2, c1=c2 হলে একটাই cell। single row বা single column rectangle-ও একই formula-তে চলে — sentinel-এর কল্যাণে আলাদা if লাগে না।

7. Brute force thinking

prefix না বানিয়ে, প্রতিটা query-তে rectangle-এর সব cell ঘুরে যোগ:

def rect_sum_brute(mat, r1, c1, r2, c2):
    total = 0
    for i in range(r1, r2 + 1):
        for j in range(c1, c2 + 1):
            total += mat[i][j]
    return total

সরল, ঠিক উত্তর দেয় — দুটো nested loop দিয়ে পুরো rectangle ঘোরে।

8. Why brute force may be slow

একটা query-তে nested loop চলে (r2-r1+1) × (c2-c1+1) বার — খারাপ ক্ষেত্রে পুরো matrix, O(R×C)। q টা query হলে মোট O(R × C × q)।

R = C = 1000, q = 100000 হলে:
  brute force: ~10^11 operation  (O(R·C·q)) — TLE
  2D prefix  : O(R·C) build + q×O(1)  ≈ 10^6 + 10^5 — দ্রুত

overlapping rectangle-এ একই cell বারবার যোগ হচ্ছে — এক dimension-এর গল্পই, এবার আরও বড় স্কেলে। precompute-এর জোরালো ডাক।

9. Better thinking

মূল insight: যেকোনো rectangle-এর sum চারটা prefix value-র যোগ-বিয়োগ। একবার 2D prefix P বানাও (O(R×C)), তারপর প্রতিটা query চারটা lookup — O(1):

def build_2d_prefix(mat):
    R, C = len(mat), len(mat[0])
    P = [[0] * (C + 1) for _ in range(R + 1)]
    for i in range(R):
        for j in range(C):
            P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]   # O(1)

build একবার, query অসংখ্যবার সস্তায়। 068-এর 2D সংস্করণ।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: এক dimension-এ overlap ছিল না (দুই term যথেষ্ট), দুই dimension-এ overlap তৈরি হয় — তাই inclusion-exclusion দিয়ে কোণা ফেরত দিতে হয়।

চার term মুখস্থ কোরো না — ছবি আঁকো: বড় থেকে উপরের পট্টি বাদ, বাঁয়ের পট্টি বাদ, কোণা একবার ফেরত। sign-এর নিয়ম: ++ (বড় ও কোণা), -- (দুই পট্টি)। build-এর formula-ও একই যুক্তি উল্টো দিকে (উপর + বাঁ − কোণা + নিজে)। ছবিতে ফিরলে formula নিজেই ফিরে আসে।

11. Step-by-step dry run

mat = [[3,1,4],[2,5,6],[1,0,2]], build করে P (উপরে section 5-এ)। query (1, 1, 2, 2) (cell 5,6,0,2):

1. বড় rectangle: P[r2+1][c2+1] = P[3][3] = 24 (পুরো matrix)
2. উপরের পট্টি বাদ: P[r1][c2+1] = P[1][3] = 8 (প্রথম সারি, কলাম 0..2)
3. বাঁয়ের পট্টি বাদ: P[r2+1][c1] = P[3][1] = 6 (প্রথম কলাম, সারি 0..2)
4. কোণা ফেরত: P[r1][c1] = P[1][1] = 3 (উপরের-বাঁ একটা cell)
5. যোগফল: 24 - 8 - 6 + 3 = 13
6. মিলিয়ে: 5 + 6 + 0 + 2 = 13 ✓

12. Python solution

def build_2d_prefix(mat):
    """2D prefix sum P; P[i][j] = (0,0)..(i-1,j-1) rectangle-এর মোট।
    P-র size (R+1) x (C+1), প্রথম সারি/কলাম sentinel 0।"""
    R, C = len(mat), len(mat[0])
    P = [[0] * (C + 1) for _ in range(R + 1)]
    for i in range(R):
        for j in range(C):
            P[i + 1][j + 1] = mat[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]
    return P


def rect_sum(P, r1, c1, r2, c2):
    """rectangle (r1,c1)..(r2,c2)-এর sum (চার প্রান্ত সহ), O(1)-এ।"""
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]


def rect_sum_brute(mat, r1, c1, r2, c2):
    """ধীর O(area) per query — মিলিয়ে দেখার জন্য।"""
    return sum(mat[i][j] for i in range(r1, r2 + 1) for j in range(c1, c2 + 1))


# --- ছোট test গুলো (সব pass করা উচিত) ---
mat = [[3, 1, 4], [2, 5, 6], [1, 0, 2]]
P = build_2d_prefix(mat)
assert P == [[0, 0, 0, 0],
             [0, 3, 4, 8],
             [0, 5, 11, 21],
             [0, 6, 12, 24]]

assert rect_sum(P, 0, 0, 2, 2) == 24     # পুরো matrix
assert rect_sum(P, 1, 1, 2, 2) == 13     # 5,6,0,2
assert rect_sum(P, 0, 0, 0, 0) == 3      # একটাই cell
assert rect_sum(P, 1, 1, 1, 1) == 5
assert rect_sum(P, 0, 1, 1, 2) == 16     # 1,4,5,6
assert rect_sum(P, 2, 0, 2, 2) == 3      # নিচের সারি

# fast আর brute সব rectangle-এ একই উত্তর কিনা (brute-force cross-check):
import random
random.seed(13)
for _ in range(80):
    R = random.randint(1, 5)
    C = random.randint(1, 5)
    m = [[random.randint(-9, 9) for _ in range(C)] for _ in range(R)]
    Pr = build_2d_prefix(m)
    for r1 in range(R):
        for r2 in range(r1, R):
            for c1 in range(C):
                for c2 in range(c1, C):
                    assert rect_sum(Pr, r1, c1, r2, c2) == rect_sum_brute(m, r1, c1, r2, c2)

print(rect_sum(P, 1, 1, 2, 2))   # 13
print(rect_sum(P, 0, 0, 2, 2))   # 24
print("সব test pass!")

13. Line-by-line explanation

P = [[0] * (C + 1) for _ in range(R + 1)]

(R+1)×(C+1) grid, প্রথম সারি ও প্রথম কলাম সব 0 — এগুলোই sentinel, যাতে formula-তে আলাদা if না লাগে।

P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]

build-এর হৃদয়। নিজের মান + উপরের prefix + বাঁয়ের prefix − উপরের-বাঁ কোণা (যেটা উপর আর বাঁ দুটোতেই গোনা হয়ে গেছে, তাই একবার বাদ)।

return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

query-র হৃদয়। বড় rectangle − উপরের পট্টি − বাঁয়ের পট্টি + কোণা (দুবার বাদ পড়া কোণা একবার ফেরত)। চারটা lookup, O(1)।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random matrix-এ সব সম্ভাব্য rectangle-এ fast আর brute মিলিয়ে দেখছে (চার-স্তর nested brute-force cross-check)। সব মিললে সব test pass!।

14. Output walkthrough

mat = [[3,1,4],[2,5,6],[1,0,2]]:

• rect_sum(P, 1, 1, 2, 2) → 24 - 8 - 6 + 3 = 13 → প্রথম print ছাপে 13
• rect_sum(P, 0, 0, 2, 2) → P[3][3] - P[0][3] - P[3][0] + P[0][0] = 24 - 0 - 0 + 0 = 24 → দ্বিতীয় print ছাপে 24
• সব assert চুপচাপ pass
• শেষে সব test pass!

ছাপা output:

13
24
সব test pass!

15. Time complexity

Build O(R×C) (প্রতিটা cell একবার), per query O(1) (চারটা lookup)। q query-তে মোট O(R×C + q)। brute-এর O(R×C×q)-এর তুলনায় বিশাল লাভ।

16. Space complexity

O(R×C) — 2D prefix array P-তে (R+1)×(C+1) ঘর। query করতে আর বাড়তি জায়গা লাগে না।

17. Common mistakes

1. কোণা ফেরত যোগ ভুলে যাওয়া — + P[r1][c1] বাদ দিলে উপরের-বাঁ কোণা দুবার বিয়োগ হয়ে থেকে যায়; sum কম আসে। এটা এই problem-এর #1 bug।
2. build-এর - P[i][j] ভুলে যাওয়া — তাহলে কোণা দুবার যোগ হয়; build নিজেই ভুল।
3. sentinel সারি/কলাম না রাখা — P (R)×(C) বানালে r1=0 বা c1=0-এর query-তে index −1 দরকার পড়ে; (R+1)×(C+1) রাখো।
4. r আর c গুলিয়ে ফেলা — P[r2+1][c2+1], [c2+1][r2+1] না। সারি আগে, কলাম পরে — ধারাবাহিক থাকো।
5. off-by-one (r2 vs r2+1) — query-তে r2+1/c2+1 দরকার (rectangle দুই প্রান্ত সহ); ভুললে শেষ সারি/কলাম বাদ পড়ে।

18. Harder problems that inherit this idea

• LeetCode — Range Sum Query 2D Immutable (https://leetcode.com/problems/range-sum-query-2d-immutable/) — ঠিক এই problem, class-আকারে।
• CSES — Forest Queries (https://cses.fi/problemset/task/1652) — 2D prefix-এর সরাসরি প্রয়োগ।
• LeetCode — Maximal Square / Matrix Block Sum (https://leetcode.com/problems/matrix-block-sum/) — 2D prefix দিয়ে প্রতিটা cell-এর চারপাশের block sum।

19. Pattern learned

2D prefix sum via inclusion-exclusion — build: নিজে + উপর + বাঁ − কোণা; query: বড় − উপর − বাঁ + কোণা। বড় শিক্ষা: এক dimension-এ overlap নেই (দুই term), দুই dimension-এ overlap তৈরি হয় — তখন Venn-চিন্তা (inclusion-exclusion) দিয়ে কোণা ফেরত দিতে হয়।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "rectangle sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]। বড় − দুই পট্টি + কোণা ফেরত (inclusion-exclusion)। চার term মুখস্থ না — ছবি আঁকো।"

পরের ধাপ → 073 — Subarray Sum Equals K (prefix + hash map, এই level-এর তারকা problem)।

ফিরে দেখা: শিকড় → 067 — Prefix Sum · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।