---
title: Fenwick (BIT, 樹狀數組)
tags: 基礎資料結構
---

:::info
題目放這裡～
- [TIOJ 1080](https://tioj.ck.tp.edu.tw/problems/1080)
- [ZJ d799](https://zerojudge.tw/ShowProblem?problemid=d799)
- [ATC DPcontest PQ](https://atcoder.jp/contests/dp/tasks/dp_q)
- [TIOJ 1869](https://tioj.ck.tp.edu.tw/problems/1869)
- [Codechef SUBARR](https://www.codechef.com/problems/SUBARR)
:::

:::success
## 樹狀數組

- 支援：單點加值，前綴和（時間複雜度 $O(logn)$ ）
- 空間複雜度：$O(n)$

const int MAXN;
int BIT[MAXN+5];

//單點加值
void add(int k, int val){
    while(k <= MAXN){
        BIT[k] += val;
        k += (k&-k);
    }
}

//前綴和
int sum(int k){
    int ret = 0;
    while(k){
        ret += BIT[k];
        k -= (k&-k);
    }
    return ret;
}

:::

:::success
## 離散化
- 當只在乎序列中的大小關係的時候，可以使用離散化，縮小數值範圍
- 其實就是排序＋編碼
:::

:::success
## 講講 ZJ d799
- [ZJ d799](https://zerojudge.tw/ShowProblem?problemid=d799)
原本數列：$a_1, a_2, a_3, ..., a_n$
＝> $a_1-0, a_2-a_1, a_3-a_2, a_4-a_3, ...$
差分數列：$d_1, d_2, d_3, d_4...$
- 區間修改，單點求值：
- 對差分數列建 BIT
- 修改：$[a_3, a_7]$ 都加上 $k$
- $d_3 = a_3-a_2 += k$
- $d_8 = a_8-a_7 -= k$
- 求值：$a_i = \sum_{1}^{j}{d_j}$
- 區間修改，區間和：
- 區間和：$[a_3, a_7]$ 的區間和
- $\sum_{3}^{7}a_i = \sum_{3}^{7}\sum_{1}^{j}{d_j}$
- $=d_1*5+d_2*5+d_3*5+d_4*4+d_5*3+d_6*2+d_7*1$
- $=(d_1+d_2+d_3+d_4+d_5+d_6+d_7)*5-(d_4*1+d_5*2+d_6*3+d_7*4)$
- $a_3 = (d_1+d_2+d_3)$
- $a_4 = (d_1+d_2+d_3+d_4)$
- $a_5 = (d_1+d_2+d_3+d_4+d_5)$
- $a_6 = (d_1+d_2+d_3+d_4+d_5+d_6)$
- $a_7 = (d_1+d_2+d_3+d_4+d_5+d_6+d_7)$
- 再建一個BIT：
- $d_1*1, d_2*2, d_3*3, ...$
- 區間和：
- $=(d_1+d_2+d_3)*5+(d_4+d_5+d_6+d_7)*8-(d_4*4+d_5*5+d_6*6+d_7*7)$
:::