# 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](../11-segment-tree-and-fenwick-tree/visual-explanation.md), [Static range sum](../11-segment-tree-and-fenwick-tree/problems/001-static-range-sum-queries.md) | Prefix difference দিয়ে range sum |
| ২ | [Fenwick tree](../11-segment-tree-and-fenwick-tree/fenwick-tree.md), [Hand-trace Fenwick jumps](../11-segment-tree-and-fenwick-tree/problems/004-hand-trace-fenwick-jumps.md) | `i & -i` এবং ১-ভিত্তিক internal index |
| ৩ | [Mutable range sum](../11-segment-tree-and-fenwick-tree/problems/005-range-sum-query-mutable.md) | Assignment থেকে delta বার করা |
| ৪ | [Segment tree](../11-segment-tree-and-fenwick-tree/segment-tree.md), [Hand-build segment tree](../11-segment-tree-and-fenwick-tree/problems/003-hand-build-segment-tree.md) | Child result merge করে parent |
| ৫ | [Dynamic range minimum](../11-segment-tree-and-fenwick-tree/problems/007-dynamic-range-min-queries.md) | 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 অপরিবর্তিত থাকবে।

```python
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]` |

```python
{
    "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],
}
```

```mermaid
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-এর ধারণা

??? success "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-এ সঠিক থাকে—এক ধাপের ফল সত্যিই অন্য ধাপে কাজে লাগে।

    [Python solution](../practice/range_queries_lab.py){ download } · [unit test](../practice/test_range_queries_lab.py){ download }।

## ৫. Test ও complexity

Repository root থেকে; download করলে দুই ফাইল `practice/`-এ রেখে:

```bash
python -m unittest discover -s practice -p 'test_range_queries_lab.py' -v
```

৯টি 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](../11-segment-tree-and-fenwick-tree/problems/016-salary-queries.md)-এর coordinate compression |
| Range inspection থেকে action | [Forest queries](../11-segment-tree-and-fenwick-tree/problems/011-forest-queries.md)-এর 2D prefix |
| Fenwick traversal ও segment traversal | [Count inversions](../11-segment-tree-and-fenwick-tree/problems/010-count-inversions-two-ways.md) |

এই lab point update ও দুই ধরনের range query মজবুত করে। [সম্পূর্ণ problem list](../11-segment-tree-and-fenwick-tree/problems/README.md)-এর বাকি pattern ধীরে ধীরে করুন।