Range query: একই হিসাব বারবার না করা¶
অধ্যায়ের সূচি · অনুশীলন ও সমাধান
একটি dashboard-এ প্রতিদিনের বিক্রি রাখা আছে। ব্যবহারকারী বারবার আলাদা date range-এর মোট বিক্রি দেখতে চান। Data অপরিবর্তিত থাকলে prefix sum যথেষ্ট। কিন্তু পুরোনো দিনের বিক্রি সংশোধন হলে পরের সব prefix বদলাতে হয়। Fenwick tree ও segment tree এমন update-এর পরে অল্প কয়েকটি সংরক্ষিত হিসাব ঠিক করে।
শেখার ক্রম¶
- Static range sum-এর নোট: prefix sum baseline।
- Segment tree-এর ধারণা: range ভাঙা, overlap, combine।
- পূর্ণ ছবি ও query trace: প্রতিটি নেওয়া ও বাদ দেওয়া segment।
- Fenwick tree:
i & -i, prefix query এবং delta update। - Implementation, তারপর অনুশীলন ও official links।
একটি প্রোগ্রাম: বিক্রির রিপোর্ট সংশোধন¶
Array [2,5,1,4]; index 0 থেকে। Query [1,3] এখানে দুই প্রান্তসহ: 5+1+4=10। index 2-এর value 1 থেকে 6 হলে নতুন উত্তর 15।
flowchart TD
all["[0..3] sum = 12"] --> l["[0..1] sum = 7"]
all --> r["[2..3] sum = 5"]
l --> a["[0..0] = 2"]
l --> b["[1..1] = 5"]
r --> c["[2..2] = 1"]
r --> d["[3..3] = 4"]| Query-তে দেখা range | সম্পর্ক | কাজ |
|---|---|---|
| [0,3] | আংশিক overlap | দুদিকে নামুন |
| [0,1] | আংশিক overlap | দুদিকে নামুন |
| [0,0] | বাইরে | Sum-এর identity 0 |
| [1,1] | সম্পূর্ণ ভেতরে | 5 নিন |
| [2,3] | সম্পূর্ণ ভেতরে | 5 নিন; নিচে নামতে হবে না |
Update-এর পরে [2,2]=6, [2,3]=10, [0,3]=17। বাম subtree-এর 7 অপরিবর্তিত। Query এখন নেয় 5+10=15।
Fenwick-এ একই data¶
Fenwick সাধারণত 1-based: [2,5,1,4]-এর element-গুলোর index 1,2,3,4।
| i | lowbit(i) | tree[i] যে range রাখে | মান |
|---|---|---|---|
| 1 | 1 | [1,1] | 2 |
| 2 | 2 | [1,2] | 7 |
| 3 | 1 | [3,3] | 1 |
| 4 | 4 | [1,4] | 12 |
prefix(3) নেয় tree[3] + tree[2] = 1+7=8; path 3→2→0। Value 1-কে 6 করতে delta=5 দিয়ে add(3,5) চালান; path 3→4→8, এবং 8 array-এর বাইরে বলে থামুন। নতুন tree[3]=6, tree[4]=17। add(3,6) করলে assignment নয়, আরও 6 যোগ হবে—এটি সাধারণ ভুল।
কী বেছে নেবেন¶
| Data ও query | সাধারণ পছন্দ | সময় |
|---|---|---|
| Static range sum | Prefix sum | Build O(n), query O(1) |
| Point update + range sum | Fenwick বা segment tree | প্রতি operation O(log n) |
| Point update + range min/max/gcd | Segment tree | প্রতি operation O(log n) |
| Static 2D rectangle sum | 2D prefix sum | Build O(rows·cols), query O(1) |
| Range update + range aggregate | উপযুক্ত lazy segment tree | Update-এর নিয়ম ও aggregate-এর সম্পর্ক আগে নির্ধারণ করুন |
Sum-এর identity 0, min-এর +∞, max-এর −∞। Query-এর বাইরে node এলে সঠিক identity ফেরাতে হবে। Min বের করতে prefixMin(r)-prefixMin(l-1) ব্যবহার করা যায় না: sum-এর মতো inverse নেই।
প্রয়োগ হিসেবে Hotel Queries-এ range max দেখেই বোঝা যায় কোনো subtree-তে যথেষ্ট room আছে কি না; থাকলে বাঁদিকে আগে নেমে প্রথম hotel পাওয়া যায়।