# 區間與搜尋
# Kadane’s Algorithm
尋找最大子陣列和:
1. 如果 curr_sum + arr[i] 還比 arr[i] 大 → 表示你「繼續累加比較好」→ 保留目前子陣列

2. 如果 arr[i] 比 curr_sum + arr[i] 還大 → 表示之前累加到負的沒救了 → 從 i 這裡重新開始一個新的子陣列
> 想法: 如果加上你會太小，那就從我開始

[演示動畫](https://miro.medium.com/v2/resize:fit:4800/format:webp/1*1V_Ax4n6iQO5LeJLnmbFsA.gif)

int kadane(const vector<int>& arr) {
    int max_sum = arr[0];  // 整體最大和
    int current_sum = arr[0];  // 當前累加和

    for (int i = 1; i < arr.size(); ++i) {
        // 決定：要繼續累加，還是從頭開始？
        current_sum = max(arr[i], current_sum + arr[i]);
        max_sum = max(max_sum, current_sum);
    }

    return max_sum;
}

# 前綴和
**定義:**
給一個陣列 a，定義 p[i] 為從 a[0] 加到 a[i] 的總和：

$𝑝[𝑖]=𝑎[0]+𝑎[1]+⋯+𝑎[𝑖]$
這樣要查詢某個區間 $[l, r]$ 的總和就可以快速計算：
$sum(l,r)=p[r]−p[l−1]$

（注意：根據陣列是否從 0 開始，有時是 p[r+1] - p[l]）

:::success
[按此可以參考簡報](https://docs.google.com/presentation/d/12nPfssZje5cNbZ56CXq58JE-GWYqC1r2/edit#slide=id.p1)
:::

#include <iostream>
using namespace std;

int main(){
    int n = 5;
    int a[n] = {1, 2, 3, 4, 5};
    int b[n];// 新陣列

    b[0] = a[0];
    for(int i=1; i<=n; i++){
        b[i] = b[i-1] + a[i];
    }

    // 1 3 6 10 15

    int l = 1, r = 3;// 取sum(a[1:3])=6+3=9
    cout << b[r] - b[l-1];
}

**新陣列的前一項都是目前的總和:**
B[n] = B[n-1] + A[n]

b[0] = a[0] = 1
b[1] = b[0] + a[1] = 1 + 2 = 3
b[2] = b[1] + a[2] = 3 + 3 = 6
b[3] = b[2] + a[3] = 6 + 4 = 10
b[4] = b[3] + a[4] = 10 + 5 = 15
# 差分
:::info
通常會用前綴和來"還原"陣列
:::
**定義:**
你要對某個區間 [l, r] 進行「加上某個值 x」的操作，使用差分可以在 O(1) 時間內完成這個區間操作：

定義一個陣列 d，使得：
$d[i]=a[i]−a[i−1], d[0]=a[0]$
反過來，原始陣列可以由 d 的前綴和還原：

$a[i]=d[0]+d[1]+⋯+d[i]$

:::warning
簡單來說就是快速將區間[L:R]內，所有人同加val
:::

a = [0] * 10
d = [0] * 11  # 差分陣列

# 對 a[2]~a[5] 加上 3
d[2] += 3
d[6] -= 3

# 對 a[4]~a[8] 加上 2
d[4] += 2
d[9] -= 2

# 求最終結果：差分前綴和
for i in range(10):
    if i == 0:
        a[i] = d[i]
    else:
        a[i] = a[i-1] + d[i]

# a = [0, 0, 3, 3, 5, 5, 2, 2, 2, 0]
# d = [0, 0, 3, 0, 2, 0, -3, 0, 0, -2, 0]

**為什麼[4:8]+2要d[9] -= 2?**
因為我們還要用前綴和來還原陣列
:::warning
差分陣列比較像是 **"標記"**，告訴前綴陣列，從這裡開始要+-多少
:::

### [差分與離散化](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FSJOpSpoOH)

## 加權前綴(力矩)


例題: APCS 支點切割

# 二分搜尋
[詳細說明](https://hackmd.io/@CLKO/ByCZ5Yoa7?type=view)

int left = 0;
int right = 9;
int target = 28;
while(true){  // 找到為止
    
    int mid = (left+right)/2;  // 取範圍的中間
    
    if(arr[mid]<target){    // 如果 mid 太小，就把下界縮到 mid+1
        left = mid+1;
    }
    else if(arr[mid]>target){   // 如果 mid 太大，就把上界縮到 mid-1
        right = mid-1;
    }
    else{
        cout << "找到了!" << endl;
        break;
    }
}

### [三分搜尋法](https://hackmd.io/@nckuacm/NCKU-AdvCP-2021-Materials/https%3A%2F%2Fhackmd.io%2F%40D4nnyLee%2FNCKU-AdvCP-2021-Search)
>/ week4/ serach
# 逆向求解
:::info
有些問題從起點出發難以前進，從終點逆算過程卻意外的容易。
:::
https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FB1uGJKKcm

---
# [預處理例題與建表](https://hackmd.io/@sa072686/cp/%2Fxpr611VXTkiwVAjCAR9CJw)