Problem link ও উৎস
- **Original source:** Classic technique (2D prefix sum, inclusion-exclusion)
- **Platform:** LeetCode Range Sum Query 2D Immutable —
, CSES Forest Queries —
- **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)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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)**-এ দিতে হবে।
### Input ও output {#6-example-input-and-output}
```text
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 লাগে না।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা শহরের মানচিত্রে জমির দাম বসানো গ্রিডে। তুমি একটা আয়তাকার এলাকার মোট দাম জানতে চাও।
তোমার কাছে আছে একটা সুবিধাজনক tool: প্রতিটা কোণের জন্য "শহরের একদম উপরের-বাঁ কোণ থেকে এই বিন্দু পর্যন্ত পুরো আয়তক্ষেত্রের মোট দাম" আগে থেকে লেখা।
মাঝের একটা rectangle-এর দাম পেতে: বড় রেকটাঙ্গল (নিচের-ডান কোণ পর্যন্ত) নাও, তার থেকে উপরের অংশ বাদ দাও, বাঁয়ের অংশ বাদ দাও। কিন্তু উপরের-বাঁ কোণার টুকরোটা **দুবার** বাদ পড়ল (একবার "উপরের"-এ, একবার "বাঁয়ের"-এ), তাই সেটা **একবার ফেরত** যোগ করো। চারটা সংখ্যা দিয়ে যেকোনো rectangle।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 মুখস্থ-নির্ভর হয়ে পড়বে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **2D prefix sum + inclusion-exclusion**।
`P[i][j]` = উপরের-বাঁ কোণ (0,0) থেকে (i-1, j-1) পর্যন্ত পুরো rectangle-এর মোট। Build:
```text
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:
```text
sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
```
বড় rectangle থেকে উপরের পট্টি বাদ, বাঁয়ের পট্টি বাদ — কিন্তু উপরের-বাঁ কোণার ব্লক দুবার বাদ পড়ল, একবার ফেরত যোগ। এটাই inclusion-exclusion।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
prefix না বানিয়ে, প্রতিটা query-তে rectangle-এর সব cell ঘুরে যোগ:
```python
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)**।
```text
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):
```python
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 নিজেই ফিরে আসে।
### ছবিতে বোঝা {#5-visual-explanation}
`mat = [[3,1,4],[2,5,6],[1,0,2]]`। build করলে `P` (size 4×4, প্রথম সারি/কলাম sentinel 0):
```text
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-এর ছবি:
```text
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-এর নাচ।
### ছোট input-এ ধাপে ধাপে {#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` ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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}
```text
P = [[0] * (C + 1) for _ in range(R + 1)]
```
(R+1)×(C+1) grid, প্রথম সারি ও প্রথম কলাম সব 0 — এগুলোই sentinel, যাতে formula-তে আলাদা if না লাগে।
```text
P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]
```
build-এর হৃদয়। নিজের মান + উপরের prefix + বাঁয়ের prefix − উপরের-বাঁ কোণা (যেটা উপর আর বাঁ দুটোতেই গোনা হয়ে গেছে, তাই একবার বাদ)।
```text
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!`।
### Output মিলিয়ে দেখা {#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:
```text
13
24
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 দুই প্রান্ত সহ); ভুললে শেষ সারি/কলাম বাদ পড়ে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Range Sum Query 2D Immutable** (