Controls
Masukkan peta hutan dan pertanyaan area persegi panjang.
Total pohon: 10
Deskripsi
Bearcu memiliki peta hutan n × n. Setiap petak bisa
kosong (.) atau berisi pohon (*).
Algoritma Prefix Sum 2D
- Build prefix sum:
ps[r][c]= jumlah pohon di (1,1)-(r,c) - Query rectangle: inclusion-exclusion formula dalam O(1)
count(y1,x1,y2,x2) = ps[y2][x2] - ps[y1-1][x2] - ps[y2][x1-1] + ps[y1-1][x1-1]
Tautan Soal
Hasil Query
| # | Area | Pohon |
|---|---|---|
| 1 | (2,2) → (3,4) | 3 |
| 2 | (3,1) → (3,1) | 1 |
| 3 | (1,1) → (2,2) | 2 |
Peta Hutan
| . | * | . | . |
| * | . | * | * |
| * | * | . | . |
| * | * | * | * |