# Prefix, difference ও contribution — তিনটি পূর্ণ ছবি

## Prefix: [2,4,1,3]

```dsa
kind: array
title: "একটি range পেতে দুটি prefix-এর বিয়োগ"
steps:
  - label: "Array: index 1 ও 2-এর যোগ চাই"
    values: [2, 4, 1, 3]
    active: [1, 2]
    pointers: {L: 1, "R−1": 2}
    note: "[1,3) range-এ ডানের সীমা 3 বাদ; নিই 4 ও 1।"
  - label: "Prefix: প্রথম kটি মানের যোগ"
    values: [0, 2, 6, 7, 10]
    active: [1, 3]
    pointers: {L: 1, R: 3}
    note: "প্রথম 3টির যোগ 7 থেকে প্রথম 1টির যোগ 2 বাদ: উত্তর 5।"
```

`[1,3)` মানে index 1 ও 2: `4+1=5`। Prefix দিয়ে `prefix[3]-prefix[1]=7-2=5`। খালি prefix রাখায় l=0 হলেও একই সূত্র।

## Difference: index 1 থেকে 3 পর্যন্ত +5

চারটি শূন্যের array-এ inclusive range `[1,3]` আপডেট করি। অতিরিক্ত শেষ ঘরটি sentinel।

| index | 0 | 1 | 2 | 3 | 4 (sentinel) |
| --- | --- | --- | --- | --- | --- |
| delta | 0 | +5 | 0 | 0 | −5 |
| চলমান যোগ | 0 | 5 | 5 | 5 | 0 |

ফল `[0,5,5,5]`। Range-এর শুরুতে +5 চালু, শেষের পরের ঘরে −5 দিয়ে বন্ধ। অনেক update হলে সব delta জমিয়ে শেষে এই একটি pass।

## Contribution: [2,4,1]-এর মাঝের 4

```mermaid
flowchart TD
    V["index 1-এর মান 4"] --> A["[4]"]
    V --> B["[2,4]"]
    V --> C["[4,1]"]
    V --> D["[2,4,1]"]
```

4 আছে চারটি subarray-তে: বাঁ সীমার 2টি × ডান সীমার 2টি পছন্দ। অবদান 16। একইভাবে 2-এর অবদান `2×1×3=6`, 1-এর `1×3×1=3`; সব subarray sum-এর মোট `6+16+3=25`।

যাচাই: ছয়টি subarray-এর যোগ 2,4,1,6,5,7; মোট 25। Minimum-এর contribution-এ এই একই count সরাসরি চলে না—আগের/পরের ছোট মানের boundary চাই।

## 2D prefix: কেন একবার ফেরত যোগ করি

```dsa
kind: grid
title: "2D prefix-এর ওপর ও বাঁয়ে একটি শূন্যের সীমানা"
steps:
  - label: "মূল matrix"
    rows: [[1, 2], [3, 4]]
    active: [[1, 1]]
    note: "শুধু নিচের ডানের ঘর 4-এর যোগ চাই।"
  - label: "Padded prefix"
    rows: [[0, 0, 0], [0, 1, 3], [0, 4, 10]]
    active: [[1, 1], [1, 2], [2, 1], [2, 2]]
    muted: [[0, 0], [0, 1], [0, 2], [1, 0], [2, 0]]
    note: "চারটি সীমার মান নিই: 10 − 3 − 4 + 1 = 4।"
```

শুধু নিচের ডানের 4 পেতে `10−3−4+1=4`। ওপরের strip ও বাঁয়ের strip বাদ দিলে 1 দুবার বাদ পড়ে; তাই সেটি একবার ফেরত দিই।

## Prefix + frequency: [1,−1,1], target 1

| নতুন prefix | খুঁজি prefix−1 | আগে কতবার ছিল? | মোট উত্তর |
| --- | --- | --- | --- |
| 1 | 0 | 1 (খালি prefix) | 1 |
| 0 | −1 | 0 | 1 |
| 1 | 0 | 2 | 3 |

প্রথমে `freq={0:1}`; প্রতিটি ধাপে খোঁজার পরে বর্তমান prefix-এর frequency বাড়াই। তিনটি subarray হলো প্রথম [1], শেষ [1], পুরো [1,−1,1]। Negative থাকলেও এই হিসাব চলে।

## Sweep line: একই সময়ে কতটি কাজ চলছে

Half-open interval A=[1,4), B=[2,3), C=[4,5)।

| সময় | event | active |
| --- | --- | --- |
| 1 | A শুরু: +1 | 1 |
| 2 | B শুরু: +1 | 2 |
| 3 | B শেষ: −1 | 1 |
| 4 | A শেষ, C শুরু: মোট 0 | 1 |
| 5 | C শেষ: −1 | 0 |

সর্বোচ্চ 2টি একসঙ্গে। Inclusive endpoint-এর প্রশ্নে একই সময়ের start/end-এর নীতি ভিন্ন হতে পারে।

[ধারণায় ফিরি](concept-notes.md) · [সব সমস্যা ও অনুশীলন](problems/README.md) · [মূল উৎস](source-map.md)