# Range query: একই হিসাব বারবার না করা

[অধ্যায়ের সূচি](README.md) · [অনুশীলন ও সমাধান](problems/README.md)

একটি dashboard-এ প্রতিদিনের বিক্রি রাখা আছে। ব্যবহারকারী বারবার আলাদা date range-এর মোট বিক্রি দেখতে চান। Data অপরিবর্তিত থাকলে prefix sum যথেষ্ট। কিন্তু পুরোনো দিনের বিক্রি সংশোধন হলে পরের সব prefix বদলাতে হয়। Fenwick tree ও segment tree এমন update-এর পরে অল্প কয়েকটি সংরক্ষিত হিসাব ঠিক করে।

## শেখার ক্রম

1. [Static range sum-এর নোট](problems/001-static-range-sum-queries.md): prefix sum baseline।
2. [Segment tree-এর ধারণা](segment-tree.md): range ভাঙা, overlap, combine।
3. [পূর্ণ ছবি ও query trace](visual-explanation.md): প্রতিটি নেওয়া ও বাদ দেওয়া segment।
4. [Fenwick tree](fenwick-tree.md): `i & -i`, prefix query এবং delta update।
5. [Implementation](implementation.py), তারপর [অনুশীলন ও official links](problems/README.md)।

## একটি প্রোগ্রাম: বিক্রির রিপোর্ট সংশোধন

Array `[2,5,1,4]`; index 0 থেকে। Query `[1,3]` এখানে **দুই প্রান্তসহ**: 5+1+4=10। index 2-এর value 1 থেকে 6 হলে নতুন উত্তর 15।

```mermaid
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](problems/015-hotel-queries.md)-এ range max দেখেই বোঝা যায় কোনো subtree-তে যথেষ্ট room আছে কি না; থাকলে বাঁদিকে আগে নেমে প্রথম hotel পাওয়া যায়।