# Segment tree ও Fenwick tree — কোন অংশের উত্তর নিচ্ছি

[অধ্যায়ের সূচি](README.md) · [সহজ ব্যাখ্যা ও বাস্তব ব্যবহার](learning-guide.md) · [অনুশীলন ও সমাধান](problems/README.md)

দুই structure-ই array-র কিছু অংশের উত্তর আগে থেকে রাখে। Query-তে দরকারি অংশগুলো নিই; update-এ শুধু বদলানো element-কে ধারণ করা অংশগুলো ঠিক করি। পাশাপাশি পড়ো: [Segment tree](segment-tree.md), [Fenwick tree](fenwick-tree.md)।

## Segment tree — ছোট range থেকে বড় range

Array `[2,5,1,4,9,3]`। প্রতিটি node-এ `[বাম index..ডান index]` এবং সেই range-এর sum লেখা। এখানে দুই প্রান্তই included।

```mermaid
flowchart TD
  root["[0..5] · sum 24"] --> l["[0..2] · sum 8"]
  root --> r["[3..5] · sum 16"]
  l --> ll["[0..1] · sum 7"]
  l --> v2["[2..2] · 1"]
  r --> rl["[3..4] · sum 13"]
  r --> v5["[5..5] · 3"]
  ll --> v0["[0..0] · 2"]
  ll --> v1["[1..1] · 5"]
  rl --> v3["[3..3] · 4"]
  rl --> v4["[4..4] · 9"]
```

Leaf একটি array element রাখে। Parent তার দুই child-এর sum রাখে। এই ছয়-element tree-তে 11টি node; সাধারণভাবে এভাবে তৈরি tree-তে `2n−1`টি node থাকে, যদিও implementation-এর allocated array বড় হতে পারে।

## Query `[1,4]` — কোন node নেব

চাই `5+1+4+9 = 19`। একটি node-এর range পুরো query-র মধ্যে থাকলে তার জমা sum সরাসরি নিই। পুরো বাইরে থাকলে বাদ দিই। আংশিক মিললে children-এ নামি।

```mermaid
flowchart TD
  root["[0..5] · আংশিক, ভাগ করো"] --> l["[0..2] · আংশিক"]
  root --> r["[3..5] · আংশিক"]
  l --> ll["[0..1] · আংশিক"]
  l --> v2["[2..2] · নাও 1"]
  ll --> v0["[0..0] · বাদ"]
  ll --> v1["[1..1] · নাও 5"]
  r --> rl["[3..4] · নাও 13"]
  r --> v5["[5..5] · বাদ"]
```

| নেওয়া range | কোন value ঢুকল | জমা sum |
| --- | --- | --- |
| `[1,1]` | 5 | 5 |
| `[2,2]` | 1 | 1 |
| `[3,4]` | 4, 9 | 13 |
| সব মিলিয়ে `[1,4]` | কোনো gap বা overlap নেই | **19** |

`[3,4]` পুরোটা নিতে পেরেছি, তাই তার দুই leaf-এ নামিনি। মোট 11টি node-এর মধ্যে 9টিতে গিয়েছি, সরাসরি উত্তর নিয়েছি 3টি থেকে। বড় tree-তে query-র দুই boundary ধরে প্রতি level-এ সীমিত সংখ্যক node ভাঙে; তাই query time `O(log n)`।

## Point update — `a[2] = 6`

আগে `a[2]=1` ছিল। এটি বদলালে কেবল সেই leaf থেকে root পর্যন্ত node-গুলোর sum বদলায়।

| ধাপ | Range | পুরোনো মান | নতুন মান |
| --- | --- | --- | --- |
| Leaf | `[2,2]` | 1 | 6 |
| Parent | `[0,2]` | 8 | `7+6 = 13` |
| Root | `[0,5]` | 24 | `13+16 = 29` |

```mermaid
flowchart TD
  root["[0..5] = 29 · বদলেছে"] --> l["[0..2] = 13 · বদলেছে"]
  root --> r["[3..5] = 16"]
  l --> ll["[0..1] = 7"]
  l --> v2["[2..2] = 6 · বদলেছে"]
  r --> rl["[3..4] = 13"]
  r --> v5["[5..5] = 3"]
  ll --> v0["[0..0] = 2"]
  ll --> v1["[1..1] = 5"]
  rl --> v3["[3..3] = 4"]
  rl --> v4["[4..4] = 9"]
```

এখন একই `query(1,4)` নেয় `[1,1] + [2,2] + [3,4]`: উত্তর `5+6+13 = 24`।

## Fenwick — প্রতিটি index একটি block

এবার **index 1 থেকে** শুরু। `lowbit(i) = i & -i`; binary-তে সবচেয়ে ডানের set bit-এর মান। `tree[i]` রাখে `[i−lowbit(i)+1, i]` range-এর sum।

??? info "n = 16-এর সব block দেখো"

    | i | lowbit(i) | Covered range | Element সংখ্যা |
    | --- | --- | --- | --- |
    | 1 | 1 | `[1,1]` | 1 |
    | 2 | 2 | `[1,2]` | 2 |
    | 3 | 1 | `[3,3]` | 1 |
    | 4 | 4 | `[1,4]` | 4 |
    | 5 | 1 | `[5,5]` | 1 |
    | 6 | 2 | `[5,6]` | 2 |
    | 7 | 1 | `[7,7]` | 1 |
    | 8 | 8 | `[1,8]` | 8 |
    | 9 | 1 | `[9,9]` | 1 |
    | 10 | 2 | `[9,10]` | 2 |
    | 11 | 1 | `[11,11]` | 1 |
    | 12 | 4 | `[9,12]` | 4 |
    | 13 | 1 | `[13,13]` | 1 |
    | 14 | 2 | `[13,14]` | 2 |
    | 15 | 1 | `[15,15]` | 1 |
    | 16 | 16 | `[1,16]` | 16 |

Odd index শুধু নিজের element রাখে। Power-of-two index নিজের আগের পুরো prefix রাখে। বড় index মানেই বড় block নয়: 13-এর block এক element, 12-এর block চার element।

## Fenwick query — `prefix_sum(13)`

বর্তমান `tree[i]` নিই, তারপর `i -= lowbit(i)` করি। এতে binary-র সবচেয়ে ডানের set bit মুছে যায়।

```mermaid
flowchart LR
  a["13 · নাও [13..13]"] -->|−1| b["12 · নাও [9..12]"]
  b -->|−4| c["8 · নাও [1..8]"]
  c -->|−8| done["0 · শেষ"]
```

| i | Binary | নেওয়া block | পরের i |
| --- | --- | --- | --- |
| 13 | `1101` | `[13,13]` | `13−1 = 12` |
| 12 | `1100` | `[9,12]` | `12−4 = 8` |
| 8 | `1000` | `[1,8]` | `8−8 = 0` |

এই তিন block যোগ করলে `[1,8] + [9,12] + [13,13]`—পুরো `[1,13]`, কোনো overlap নেই। 13-এর binary-তে তিনটি set bit, তাই তিনটি block নিয়েছি।

## Fenwick update — `add(5, +10)`

Element 5-কে 10 বাড়ালে সেটিকে ধারণ করা সব block-এর sum 10 বাড়াতে হবে। বর্তমান `tree[i]` বদলাই, তারপর `i += lowbit(i)` করি। এখানে `n=16`।

```mermaid
flowchart LR
  a["5 · [5..5]"] -->|+1| b["6 · [5..6]"]
  b -->|+2| c["8 · [1..8]"]
  c -->|+8| d["16 · [1..16]"]
  d -->|+16| stop["32 > n · শেষ"]
```

| i | Binary | কোন entry বাড়ে | পরের i |
| --- | --- | --- | --- |
| 5 | `0101` | `tree[5] += 10` | 6 |
| 6 | `0110` | `tree[6] += 10` | 8 |
| 8 | `1000` | `tree[8] += 10` | 16 |
| 16 | `10000` | `tree[16] += 10` | 32; থামি |

প্রতিটি visited block-এ index 5 আছে। Update-এর পথ বড় block-এর দিকে যায়; prefix query-র পথ overlap ছাড়া আগের block-এর দিকে যায়। দুটোরই সময় `O(log n)`।

## একই data, আলাদা storage

চার element `[2,5,1,4]`; এই তুলনায় দুই structure-তেই বাইরের index 1 থেকে ধরছি। Segment tree-এর সব node:

```mermaid
flowchart TD
  all["[1..4] · sum 12"] --> l["[1..2] · sum 7"]
  all --> r["[3..4] · sum 5"]
  l --> a["[1..1] · 2"]
  l --> b["[2..2] · 5"]
  r --> c["[3..3] · 1"]
  r --> d["[4..4] · 4"]
```

Fenwick storage মাত্র চারটি entry: `tree[1]=2`, `tree[2]=7`, `tree[3]=1`, `tree[4]=12`। Segment tree-এর মতো প্রতিটি অর্ধের node এখানে নেই; আছে lowbit-নির্ধারিত block।

| প্রশ্ন | Segment tree | Fenwick sum tree |
| --- | --- | --- |
| `[2,4]`-এর sum | `[2,2] + [3,4] = 5+5` | `prefix(4)−prefix(1) = 12−2` |
| Element 3-এ +5 | Leaf, `[3,4]`, `[1,4]` বদলায় | `tree[3]`, `tree[4]` বদলায় |
| Range min | Combine-এ min ব্যবহার করা যায় | সাধারণ prefix subtraction পদ্ধতি চলে না |

নিজে করো: update-এর পরে এই দুই structure দিয়ে আবার `[2,4]`-এর sum বের করো। দুই উত্তরই **15** হওয়া উচিত।