Range Queries — গুদামের stock monitor¶
পাশাপাশি কয়েকটি গুদামে পণ্যের stock আছে। কখনও একটি গুদামের stock বদলাবে, কখনও একটি range-এর মোট stock ও সবচেয়ে কম stock-এর গুদাম জানতে চাইবেন। একটি refill নির্দেশ সেই range-এর সবচেয়ে দুর্বল একটি গুদামকে threshold পর্যন্ত ভরবে।
এই lab-এ দুটি data structure একসঙ্গে কাজে লাগবে: Fenwick tree মোট stock রাখবে, segment tree minimum stock ও তার index রাখবে। একই update দুটিতে না পৌঁছালে রিপোর্ট ভুল হবে।
কোর্সের সম্পর্ক: এটি efficient query ও optimization-এর অতিরিক্ত practice। Screenshot-এর module title থেকে Fenwick/segment tree-কে Microsoft কোর্সের নির্দিষ্ট lesson বলে চিহ্নিত করা হচ্ছে না।
১. আগে পড়ুন, তারপর ছোট problem করুন¶
| ক্রম | উপকরণ | লক্ষ্য |
|---|---|---|
| ১ | Visual explanation, Static range sum | Prefix difference দিয়ে range sum |
| ২ | Fenwick tree, Hand-trace Fenwick jumps | i & -i এবং ১-ভিত্তিক internal index |
| ৩ | Mutable range sum | Assignment থেকে delta বার করা |
| ৪ | Segment tree, Hand-build segment tree | Child result merge করে parent |
| ৫ | Dynamic range minimum | Point update-এর পরে ancestor বদলানো |
দুটি ছোট array-এ ২ ও ৪ নম্বর হাতে করুন। একটি tree sum-এর জন্য, আরেকটি minimum-এর জন্য—কোন operation invertible তা বোঝার পর শুরু করুন।
২. সমস্যা ও input/output¶
inventory_report(initial, events, threshold) লিখুন। External index সবসময় ০-ভিত্তিক, query range [left, right): left থাকবে, right থাকবে না।
| Event | অর্থ |
|---|---|
("set", index, value) |
একটি গুদামের stock নতুন value হবে |
("inspect", left, right) |
Range-এর total, minimum, minimum-এর index ও refill-এ লাগবে কত তা রিপোর্ট করুন |
("refill", left, right) |
একই update-এর আগের report দিন; তারপর minimum গুদামটির stock threshold পর্যন্ত বাড়ান |
Minimum সমান হলে ছোট index নিন। needed = max(0, threshold - minimum)। Threshold-এর ওপরে থাকলে stock কমাবেন না। Refill একবারে কেবল নির্বাচিত একটি গুদাম বদলায়; range-এর সব গুদাম নয়। set-এর আলাদা report নেই। শেষে reports ও final stock ফেরত দিন।
সীমা: 1 ≤ n ≤ 100,000, event সর্বোচ্চ 100,000; stock, threshold ও assignment value পূর্ণসংখ্যা 0..10⁹; query-তে 0 ≤ left < right ≤ n। Invalid event, index, empty range বা negative stock-এ ValueError। Input list অপরিবর্তিত থাকবে।
inventory_report(
[5, 1, 4, 1],
[("inspect", 0, 4), ("refill", 0, 4),
("set", 2, 0), ("inspect", 1, 4)],
threshold=3,
)
| Event | Range total, minimum@index | Needed | Event-এর পরে stock |
|---|---|---|---|
inspect [0,4) |
11, 1@1 |
2 | [5,1,4,1] |
refill [0,4) |
11, 1@1 |
2 | [5,3,4,1] |
| set index 2 → 0 | report নেই | — | [5,3,0,1] |
inspect [1,4) |
4, 0@2 |
3 | [5,3,0,1] |
{
"reports": [
{"kind": "inspect", "range": (0, 4), "total": 11,
"minimum": 1, "index": 1, "needed": 2},
{"kind": "refill", "range": (0, 4), "total": 11,
"minimum": 1, "index": 1, "needed": 2},
{"kind": "inspect", "range": (1, 4), "total": 4,
"minimum": 0, "index": 2, "needed": 3},
],
"stock": [5, 3, 0, 1],
}
flowchart TD
stock["বর্তমান stock array"] --> bit["Fenwick tree\nprefix sum"]
stock --> seg["Segment tree\nminimum, index"]
bit --> report["Range report"]
seg --> report
report --> refill["প্রয়োজনে weakest index refill"]
refill --> stock
stock --> update["একই point update দুই tree-তেই"]৩. Guided milestones¶
A — Fenwick total¶
add(index, delta) এবং prefix(end) লিখুন। Prefix-এর অর্থ প্রথম end-টি গুদামের stock: [0,end)। তাই range_sum(l,r) = prefix(r) - prefix(l)।
Invariant: tree-এর প্রতিটি internal index তার lowbit-দৈর্ঘ্যের block sum রাখে। Public index যাচাই করে তারপর index += 1 করুন; ভুল করে add(-1, ...) গ্রহণ করলে internal index 0-তে loop আটকে যেতে পারে।
Checkpoint: example-এ prefix(0)=0, prefix(4)=11, [1,4) sum 6।
B — Minimum segment tree¶
Leaf-এ (value, index) রাখুন। Parent হবে দুই child tuple-এর minimum। Python tuple comparison value সমান হলে ছোট index বেছে নেবে। Extra padding leaf-এ (infinity, -1) রাখুন।
Invariant: প্রতিটি node তার interval-এর minimum এবং প্রথম minimum index রাখে। Checkpoint: [5,1,4,1]-এর minimum (1,1); index 1-এ stock 3 হলে minimum (1,3)।
C — এক জায়গায় update¶
assign(index, value) helper বানান: পুরোনো stock থেকে delta হিসাব করে Fenwick-এ add, segment tree-তে set, শেষে stock copy বদলান। set ও refill—দুটিই এই helper ব্যবহার করবে।
Hint: assignment value-কে সরাসরি Fenwick delta হিসেবে যোগ করা যাবে না। Checkpoint: stock 1 → 3 হলে delta +2; 4 → 0 হলে delta -4।
D — Inspect থেকে refill সিদ্ধান্ত¶
দুই tree query করে report বানান। refill হলে report লেখার পরে weakest index-এ threshold assign করুন, যদি needed positive হয়। এরপরের query নতুন state দেখবে।
Checkpoint: example-এর final total [1,4) হলো 4; refill report-এ পুরোনো total 11, নতুন 13 নয়।
৪. Reference solution-এর ধারণা¶
Sum ও minimum কেন আলাদা রাখছি
Prefix sum থেকে দুটি prefix বিয়োগ করে range sum পাওয়া যায়। Minimum-এর জন্য সেই বিয়োগ সম্ভব নয়: দুটি prefix minimum জানলেও মাঝের range-এর minimum নির্ধারিত হয় না। তাই segment tree query-তে range-টিকে disjoint block-এ ভাগ করে তাদের minimum merge করা হয়।
একক assignment helper দুটি structure একই stock state-এ রাখে। Refill-এর বেছে নেওয়া index segment tree থেকে আসে, আর পরিবর্তনের পর total Fenwick-এ সঠিক থাকে—এক ধাপের ফল সত্যিই অন্য ধাপে কাজে লাগে।
৫. Test ও complexity¶
Repository root থেকে; download করলে দুই ফাইল practice/-এ রেখে:
৯টি test method worked example, one warehouse, tie-breaking, no-op refill, input preservation, invalid events, non-power-of-two length ও direct helper bounds দেখে। ৮০টি seeded random case-এ ৪০টি করে event সাধারণ array দিয়ে simulate করে পুরো report মেলানো হয়।
Reference build-এ Fenwick তৈরি O(n log n), segment tree O(n)। প্রতিটি set/inspect/refill O(log n); মোট O((n+q) log n)। Tree-এর space O(n), report-সহ O(n+q)।
৬. Coverage ও পরের ধাপ¶
| এখানে ব্যবহার | আলাদা pattern |
|---|---|
| Prefix sum, point add/assign | Range add + range sum |
| Segment-tree minimum ও tie index | Lazy propagation |
| একাধিক aggregate-এর consistent update | Salary queries-এর coordinate compression |
| Range inspection থেকে action | Forest queries-এর 2D prefix |
| Fenwick traversal ও segment traversal | Count inversions |
এই lab point update ও দুই ধরনের range query মজবুত করে। সম্পূর্ণ problem list-এর বাকি pattern ধীরে ধীরে করুন।