011 — Forest Queries¶
Source¶
- Original source: CSES Problem Set — "Forest Queries"
- Platform: CSES Problem Set — "Forest Queries"
- Topic: segment tree and fenwick tree
- Difficulty: Medium
- Pattern: 2D prefix sums (static — tree লাগে না!)
- Basic idea inherited from: math level 5 prefix sums, grids
1. Problem in simple words¶
একটা n × n grid দেওয়া, প্রতিটা cell-এ হয় একটা গাছ (*) আছে নয় নেই (.)। তারপর অনেকগুলো query: প্রতিবার একটা rectangle-এর দুই কোণ (উপর-বাঁ আর নিচ-ডান) দেওয়া হয়, আর জিজ্ঞেস করা হয় ওই rectangle-এ মোট কয়টা গাছ। Grid কখনো বদলায় না — পুরোপুরি static।
2. Which basic idea does this inherit from?¶
এটা 2D prefix sums আর grids-এর উপর দাঁড়িয়ে। 1D prefix sums তুমি ../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-এ দেখেছ; এটা ঠিক সেটারই দুই-মাত্রার রূপ। 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)।
6. Real-life analogy¶
ভাবো একটা শহরের map, প্রতি ব্লকে কয়টা বাড়ি লেখা। কেউ যদি বারবার নানা আয়তাকার এলাকার মোট বাড়ি জানতে চায়, প্রতিবার গুনতে যাওয়া বোকামি। বরং একবার "শহরের উত্তর-পশ্চিম কোণ থেকে এই point পর্যন্ত মোট কয়টা বাড়ি" — এমন running total বানিয়ে রাখো; তারপর যেকোনো rectangle চারটা running total-এর যোগ-বিয়োগে এক নিমেষে।
7. Visual explanation¶
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]
8. Example input and output¶
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
9. Brute force thinking¶
সরল চিন্তা: প্রতি query-তে rectangle-এর প্রতিটা cell দুই nested loop-এ ঘুরে গাছ গোনা।
একটা 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 কি যথেষ্ট? এখানে উত্তর হ্যাঁ।
14. Step-by-step dry run¶
উপরের grid, P 1-indexed (row/col 0 padding শূন্য)। কয়েকটা entry:
P[1][2] = grid[1][2] + P[0][2] + P[1][1] - P[0][1] = 1 + 0 + 0 - 0 = 1।P[2][2] = grid[2][2] + P[1][2] + P[2][1] - P[1][1] = 0 + 1 + 1 - 0 = 2।- পুরো table ভরার পর
P[4][4] = 6(মোট গাছ)। - query rows 2..3, cols 2..4 =
P[3][4] - P[1][4] - P[3][1] + P[1][1]। - মান বসিয়ে =
4 - 1 - 1 + 0 = 2। ✓ (section 8-এর হাতের গোনার সাথে মিলল)
15. Python solution¶
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 করতে।
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!।
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।
21. Which basic problem this inherits from¶
ভিত্তি: 1D prefix sums (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/) — এটা তারই 2D রূপ। কোনো update নেই বলেই এটা এই tracker-এর "over-building ধরার" problem-গুলোর একটা (#1, #2, #8-এর মতো)।
22. Similar harder problems¶
- Range Sum Query 2D — Immutable (একই 2D prefix idea, class API) — https://leetcode.com/problems/range-sum-query-2d-immutable/
- Dynamic Range Sum Queries (update যোগ হলে তখন tree/2D BIT লাগবে) — CSES 1648 (#6)
- Forest Queries II (update-সহ 2D — তখন 2D Fenwick) — CSES "Forest Queries II"
23. Pattern learned¶
2D prefix sums: static grid-এ rectangle-sum = চারটা corner-prefix-এর inclusion-exclusion, প্রতি query O(1)। সবচেয়ে বড় শিক্ষা — static দেখলে আগে prefix table ভাবো, tree নয়।
24. Final summary¶
ভবিষ্যতের আমাকে: 2D static range-sum মানেই 2D prefix table + inclusion-exclusion (P[r2][c2] - উপর - বাঁ + কোণা)। Tree-র লোভ সামলাও — update নেই মানে tree নেই। Update এলে (Forest Queries II) তবেই 2D Fenwick-এ যাও।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।