Problem link ও উৎস
- **Original source:** CSES Problem Set — "Forest Queries"
- **Platform:** [CSES 1652 · Forest Queries](https://cses.fi/problemset/task/1652)
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Medium
- **Pattern:** 2D prefix sums (static — tree লাগে না!)
- **Basic idea inherited from:** math level 5 prefix sums, grids
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `n × n` grid দেওয়া, প্রতিটা cell-এ হয় একটা গাছ (`*`) আছে নয় নেই (`.`)। তারপর অনেকগুলো query: প্রতিবার একটা rectangle-এর দুই কোণ (উপর-বাঁ আর নিচ-ডান) দেওয়া হয়, আর জিজ্ঞেস করা হয় ওই rectangle-এ মোট কয়টা গাছ। Grid কখনো বদলায় না — **পুরোপুরি static**।
```text
grid (n=4): query: rectangle (row 2..3, col 2..4) -এ কয়টা গাছ?
. * . .
* . * .
. . . *
* * . .
```
### Input ও output {#8-example-input-and-output}
```text
grid (n=4, 1=গাছ):
0 1 0 0
1 0 1 0
0 0 0 1
1 1 0 0
query rows 2..3, cols 2..4 -> cells: (2,2)=0 (2,3)=1 (2,4)=0
(3,2)=0 (3,3)=0 (3,4)=1
-> মোট = 2
query rows 1..4, cols 1..4 -> পুরো grid = 6
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা শহরের map, প্রতি ব্লকে কয়টা বাড়ি লেখা। কেউ যদি বারবার নানা আয়তাকার এলাকার মোট বাড়ি জানতে চায়, প্রতিবার গুনতে যাওয়া বোকামি। বরং একবার "শহরের উত্তর-পশ্চিম কোণ থেকে এই point পর্যন্ত মোট কয়টা বাড়ি" — এমন running total বানিয়ে রাখো; তারপর যেকোনো rectangle চারটা running total-এর যোগ-বিয়োগে এক নিমেষে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **2D prefix sums আর grids**-এর উপর দাঁড়িয়ে। 1D prefix sums তুমি [../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এ দেখেছ; এটা ঠিক সেটারই দুই-মাত্রার রূপ। Grid static বলে এখানে কোনো tree-র দরকারই নেই।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **inclusion-exclusion**। একটা rectangle-এর sum পাওয়া যায় চারটা corner-prefix থেকে: বড় rectangle থেকে উপরের strip আর বাঁয়ের strip বাদ দাও, তারপর দুবার-বাদ-পড়া কোণাটা আবার যোগ করো। একবার prefix table বানালে প্রতি query O(1)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **2D prefix-sum table** `P`, যেখানে `P[i][j]` = `(1,1)` থেকে `(i,j)` পর্যন্ত sub-rectangle-এর গাছ-সংখ্যা। **কোনো segment tree বা Fenwick tree নয়** — কারণ কোনো update নেই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Static grid + অনেক range query = prefix sums-এর আদর্শ ক্ষেত্র। Tree বানানো এখানে over-engineering — `../../README` decision drill-এর ভাষায়: *"no updates? → prefix sums (do not build a tree for a frozen array)"*। 2D prefix table O(n^2)-এ বানিয়ে প্রতি query O(1)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতি query-তে rectangle-এর প্রতিটা cell দুই nested loop-এ ঘুরে গাছ গোনা।
```text
total = 0
for r in range(r1, r2+1):
for c in range(c1, c2+1):
total += grid[r][c]
```
একটা query-র জন্য ঠিক, আর এটাই আমাদের brute-force reference।
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি query O(n^2) (rectangle পুরো grid হতে পারে)। q-টা query থাকলে O(q · n^2)। n = 1000, q = 200,000 হলে অসম্ভব বড় — TLE। 2D prefix table প্রতি query **O(1)**-এ নামায়, একবার O(n^2) precompute-এর বিনিময়ে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **যেকোনো rectangle = চারটা corner-prefix-এর সমষ্টি**। প্রতি query-তে আলাদা করে গোনার দরকার নেই — চারটা precomputed মান পড়ে inclusion-exclusion করলেই হয়। এটাই 1D `prefix[r] - prefix[l-1]`-এর 2D সাধারণীকরণ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`P[i][j]` বানাও running recurrence-এ: `P[i][j] = grid[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]` (উপর আর বাঁ যোগ করো, double-counted কোণা বিয়োগ)। তারপর প্রতি query চারটা lookup-এ O(1)। 1-indexed padding (0-তম row/col শূন্য) boundary সহজ করে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "rectangle-টা ঘুরে গুনব" ভাবার বদলে ভাবো "চারটা origin-anchored prefix-এর যোগ-বিয়োগ"। Static grid দেখলেই প্রথম প্রশ্ন হওয়া উচিত — tree নয় — *prefix table কি যথেষ্ট?* এখানে উত্তর হ্যাঁ।
### ছবিতে বোঝা {#7-visual-explanation}
```text
inclusion-exclusion দিয়ে rectangle (r1,c1)..(r2,c2):
c1-1 c2
| |
----+-----+---- r1-1
| A | B |
----+---+---+---
| C | D | <- চাই শুধু D
----+---+---+--- r2
P[r2][c2] = A + B + C + D (পুরো বড় rectangle)
P[r1-1][c2] = A + B (উপরের strip বাদ)
P[r2][c1-1] = A + C (বাঁয়ের strip বাদ)
P[r1-1][c1-1] = A (কোণা A দুবার বাদ পড়েছে -> ফেরত যোগ)
D = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
উপরের grid, `P` 1-indexed (row/col 0 padding শূন্য)। কয়েকটা entry:
1. `P[1][2] = grid[1][2] + P[0][2] + P[1][1] - P[0][1] = 1 + 0 + 0 - 0 = 1`।
2. `P[2][2] = grid[2][2] + P[1][2] + P[2][1] - P[1][1] = 0 + 1 + 1 - 0 = 2`।
3. পুরো table ভরার পর `P[4][4] = 6` (মোট গাছ)।
4. query rows 2..3, cols 2..4 = `P[3][4] - P[1][4] - P[3][1] + P[1][1]`।
5. মান বসিয়ে = `4 - 1 - 1 + 0 = 2`। ✓ (section 8-এর হাতের গোনার সাথে মিলল)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class Grid2D:
"""STATIC 2D range-sum। কোনো update নেই -> tree নয়, 2D prefix table।
grid 0-indexed দেওয়া; ভেতরে 1-indexed prefix P রাখি যাতে boundary সহজ।
query(r1, c1, r2, c2): inclusive rectangle, 0-indexed corners।"""
def __init__(self, grid):
self.R = len(grid)
self.C = len(grid[0]) if self.R else 0
# P 1-indexed, (R+1) x (C+1), row/col 0 হলো padding শূন্য
self.P = [[0] * (self.C + 1) for _ in range(self.R + 1)]
for i in range(1, self.R + 1):
for j in range(1, self.C + 1):
self.P[i][j] = (grid[i - 1][j - 1]
+ self.P[i - 1][j]
+ self.P[i][j - 1]
- self.P[i - 1][j - 1])
def query(self, r1, c1, r2, c2): # inclusive, 0-indexed corners
# 1-indexed-এ shift করে inclusion-exclusion
r1 += 1; c1 += 1; r2 += 1; c2 += 1
return (self.P[r2][c2]
- self.P[r1 - 1][c2]
- self.P[r2][c1 - 1]
+ self.P[r1 - 1][c1 - 1])
def brute(grid, r1, c1, r2, c2):
# obviously-correct reference, rectangle ঘুরে গোনে
total = 0
for r in range(r1, r2 + 1):
for c in range(c1, c2 + 1):
total += grid[r][c]
return total
# ---- tests ----
grid = [
[0, 1, 0, 0],
[1, 0, 1, 0],
[0, 0, 0, 1],
[1, 1, 0, 0],
]
g = Grid2D(grid)
# section 8-এর হাতের উত্তর (0-indexed corners)
assert g.query(1, 1, 2, 3) == 2 # rows 2..3, cols 2..4 (1-indexed ভাষায়)
assert g.query(0, 0, 3, 3) == 6 # পুরো grid
assert g.query(0, 0, 0, 0) == 0 # একটা cell, খালি
assert g.query(1, 0, 1, 0) == 1 # একটা cell, গাছ আছে
# সব সম্ভাব্য rectangle exhaustively brute-এর সাথে মেলানো
for r1 in range(len(grid)):
for c1 in range(len(grid[0])):
for r2 in range(r1, len(grid)):
for c2 in range(c1, len(grid[0])):
assert g.query(r1, c1, r2, c2) == brute(grid, r1, c1, r2, c2)
# random grid-এও সব rectangle মেলানো
import random
for _ in range(40):
R = random.randint(1, 6)
C = random.randint(1, 6)
rg = [[random.randint(0, 1) for _ in range(C)] for _ in range(R)]
gg = Grid2D(rg)
for r1 in range(R):
for c1 in range(C):
for r2 in range(r1, R):
for c2 in range(c1, C):
assert gg.query(r1, c1, r2, c2) == brute(rg, r1, c1, r2, c2)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.P` — `(R+1) × (C+1)`, 1-indexed; 0-তম row/col padding শূন্য, তাই `i-1`/`j-1` সবসময় নিরাপদ।
- build recurrence — `grid[i-1][j-1] + উপর + বাঁ - কোণা`: double-counted overlap বিয়োগ।
- `query` — corners 1-indexed-এ shift করে inclusion-exclusion-এর চারটা term।
- `brute` — rectangle ঘুরে গোনে, O(1) version verify করতে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`Grid2D(grid)` O(R·C)-তে prefix table বানায়। `query(1,1,2,3)` চারটা lookup-এর যোগ-বিয়োগে 2 দেয় (section 14)। তারপর fixed grid-এর প্রতিটা rectangle, এবং 40-টা random grid-এর প্রতিটা rectangle, brute-এর সাথে মেলে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**Build O(n^2)** (প্রতি cell একবার), **প্রতি query O(1)** (চারটা lookup)। q query-তে মোট O(n^2 + q)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n^2)** — `(n+1) × (n+1)` prefix table।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- 1-indexed padding না রাখা — তখন `i-1`/`j-1`-এ index-out-of-range বা boundary off-by-one।
- inclusion-exclusion-এ শেষ `+ P[r1-1][c1-1]` term ভুলে যাওয়া — দুবার-বাদ-পড়া কোণা ফেরত না দিলে undercount।
- Static grid-এ tree বানিয়ে ফেলা — pass করলেও spirit-এ ভুল; এখানে prefix table-ই সঠিক হাতিয়ার।
- query-তে inclusive vs exclusive corner গুলিয়ে ফেলা — এই note জুড়ে inclusive convention।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: 1D prefix sums ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)) — এটা তারই 2D রূপ। কোনো update নেই বলেই এটা এই tracker-এর "over-building ধরার" problem-গুলোর একটা (#1, #2, #8-এর মতো)।
### পরের অনুশীলন {#22-similar-harder-problems}
- Range Sum Query 2D — Immutable (একই 2D prefix idea, class API) —