---
tags: code
---

# Fenwick Tree (樹狀數組)
[TOC]
## Usage
- 前綴和
- 區間更新 & 查詢
- 可擴展到 2D BIT

## Definition
Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. (from Wikipedia)

## Introduction
### lowbit
- 二進位最後一個 1 的位置所代表的數值。
`e.g.` $13=0b1101\ \implies\ lowbit=0b0001=1$
`e.g.` $12=0b1100\ \implies\ lowbit=0b0100=4$
- 必為 $2$ 的冪次。
- lowbit(x) = (x & -x)

### BIT
- 節點存 $[i-lowbit(i)+1,i]$ 的和。
- 父節點為 $i-lowbit(i)$。
- 第一行為原數組，第二到第四行依次填入數字。
- 方便起見，此處對此數組的索引為從 $1$ 開始。
- 利用圖中已構造好的樹狀數組，則：

prefixSum(13) = prefixSum(0b00001101)
= BIT[13] + BIT[12] + BIT[8]
= BIT[0b00001101] + BIT[0b00001100] + BIT[0b00001000]

### Sum

可發現並不是一棵二元樹，
Binary 是指「二進位」。
### Update
### 時間複雜度
- 修改 $O(\log n)$
- 查詢 $O(\log n)$

## 單點修改、區間查詢 BIT
### `建構`
#### $O(n\log n)$ 建構
藉由以下的 `更新` 函式，
一個點一個點更新即可，
$\implies$ 時間複雜度 $O(n\log n)$。
#### $O(n)$ 建構
可以知道，
bit[i] 存的是 $[i-lowbit(i)+1,i]$ 的和，
可以先把陣列以 $O(n)$ 的方式作一次前綴和，
再一個 $O(n)$ 建構 $bit[i]=a[i]-a[i-lowbit(i)]$，
$\implies$ 時間複雜度 $O(n)$。

### `查詢(前綴和)`

#define lowbit(x) (x & -x)
#define ll long long
ll sum(ll* bit, int x) {
	ll ret = 0;
	for (; x; x -= lowbit(x))
		ret += bit[x];
	return ret;
}

### `更新`

#define lowbit(x) (x & -x)
#define ll long long
void upd(ll* bit, int x, int v) {
	// n 是 BIT 的 size
	for (; x <= n; x += lowbit(x))
		bit[x] += v;
}

## 區間修改、單點查詢 BIT
### `原理`
通過差分把這個「區間修改、單點查詢」的問題轉化為「單點修改、區間查詢」

要記錄的數組是 $a[1:n]$，
假設：
$\begin{cases}d[i]=a[i]−a[i−1]&,i=2\sim n \\d[i]=a[i]&,i=1\end{cases}$

得到：
$\implies a[i]=d[1]+d[2]+\dots+d[i]=\sum\limits_{k=1}^i d[k]$。

所以在 $BIT$ 中實際存儲的是數組 $d[1:n]$

### `修改`
目標是給 $a[L:R]$ 全部加上 $x$，
那麼可以發現 $d[L+1]$, $d[L+2]$, $\dots$, $d[R]$ 都沒有變化。
而變化的只有 $d[L]$ 增加了 $x$、$d[R+1]$ 減少了 $x$。
所以只需要 $add(L,x)$, $add(R+1,-x)$ 即可。

### `查詢`
要單點查詢 $a[pos]$，
由上可知 $a[pos]=d[1]+d[2]+\dots+d[pos]$，
那麼原來的 $sum(pos)$ 函數不用修改，
就正好能返回 $a[pos]$ 的值。

## 區間修改，區間查詢 BIT
### `原理`
由於目標記錄的是數組 $a[1:n]$，
而實際存儲的是 $d[1:n]$，
那麼已經實現了區間修改。
前綴和：
$a[1]+a[2]+⋯+a[i]\\=d[1]\times i+d[2]\times (i−1)+\dots+d[i]\times 1\\=([d[1]\times (i+1)+d[2]\times (i+1)+\dots+d[i]\times (i+1))−(d[1]\times 1+d[2]\times 2+\dots+d[i]\times i)\\=(i+1)\times (d[1]+d[2]+\dots+d[i])−(d[1]\times 1+d[2]\times 2+\dots+d[i]\times i)$
在原來的數組 $C[i]$ 記錄 $d[i]$ 的基礎上，再搞一個數組 $C2[i]$ 記錄 $d[i]×i$ 即可。

:::spoiler `code`

// author: giver
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) (x & -x)
using namespace std;
ll bit1[1000005], bit2[1000005], a[1000005];
int T;
ll sum(ll *bit, int x) {
	ll ret = 0;
	while (x) {
		ret += bit[x];
		x -= lowbit(x);
	}
	return ret;
}
void upd(ll *bit, int x, ll v) {
	while (x <= T) {
		bit[x] += v;
		x += lowbit(x);
	}
}
ll qry(int x) {
	return (x + 1) * sum(bit1, x) - sum(bit2, x);
}
ll qry(int l, int r) {
	return qry(r) - qry(l - 1);
}
void upd(int l, int r, ll v) {
	upd(bit1, l, v); upd(bit2, l, l * v);
	upd(bit1, r + 1, -v); upd(bit2, r + 1, (r + 1) * -v);
}
int main() {
	cin.tie(0), ios::sync_with_stdio(0);
	int n, q; cin >> n >> q; T = n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) bit1[i] = a[i] - a[i - lowbit(i)];
	for (int i = n; i; i--) a[i] -= a[i - 1];
	for (int i = 1; i <= n; i++) a[i] = a[i - 1] + a[i] * i;
	for (int i = 1; i <= n; i++) bit2[i] = a[i] - a[i - lowbit(i)];
	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int l, r; cin >> l >> r;
			cout << qry(l, r) << "\n";
		}
		else {
			int l, r; ll k; cin >> l >> r >> k;
			upd(l, r, k);
		}
	}
	return 0;
}

:::

## Problems
:::spoiler `ZJ d788. 排名順序`

#include <streambuf>
#include <iostream>
#include <cstring>
#define lowbit(x) (x & -x)

using namespace std;

namespace IO {
bool rit(auto& re) {
	re = 0;
	char c = cin.rdbuf()->sbumpc();
	while (!isdigit(c)) {
		if (c == EOF)
			return false;
		c = cin.rdbuf()->sbumpc();
	}
	while (isdigit(c))
		re = re * 10 + c - '0', c = cin.rdbuf()->sbumpc();
	return true;
}
void wit(auto x) {
	char tmp[20], cur = 0;
	do tmp[cur++] = x % 10 + '0', x /= 10; while (x);
	while (cur)
		cout.rdbuf()->sputc(tmp[--cur]);
	cout.rdbuf()->sputc('\n');
}
}

using namespace IO;

int bit[100001], n, r;

int sum(int* bit, int x) {
	int ret = 0;
	while (x)
		ret += bit[x], x -= lowbit(x);
	return ret;
}

void upd(int* bit, int x, int v) {
	while (x <= n)
		bit[x] += v, x += lowbit(x);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	while (rit(n)) {
		memset(bit, 0, (n + 1) * 4);
		for (int i = 1; i <= n; i++) {
			rit(r);
			upd(bit, r, 1);
			wit(i - sum(bit, r - 1));
		}
	}
}

:::

:::spoiler `ZJ d794. 世界排名`

#include <algorithm>
#include <streambuf>
#include <iostream>
#include <cstring>
#define lowbit(x) (x & -x)

using namespace std;

namespace IO {
bool rit(auto& re) {
	re = 0;
	char c = cin.rdbuf()->sbumpc();
	while (!isdigit(c)) {
		if (c == EOF)
			return false;
		c = cin.rdbuf()->sbumpc();
	}
	while (isdigit(c))
		re = re * 10 + c - '0', c = cin.rdbuf()->sbumpc();
	return true;
}
void wit(auto x) {
	char tmp[20], cur = 0;
	do tmp[cur++] = x % 10 + '0', x /= 10; while (x);
	while (cur)
		cout.rdbuf()->sputc(tmp[--cur]);
	cout.rdbuf()->sputc('\n');
}
}

using namespace IO;

int n;

int sum(int* bit, int x) {
	int ret = 0;
	while (x)
		ret += bit[x], x -= lowbit(x);
	return ret;
}

void upd(int* bit, int x, int v) {
	while (x <= n)
		bit[x] += v, x += lowbit(x);
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	while (rit(n)) {
		int bit[n + 1], a[n], tmp[n];
		memset(bit, 0, (n + 1) * 4);
		for (int i = 0, x; i < n; i++)
			rit(x), a[i] = tmp[i] = x;
		sort(tmp, tmp + n);
		for (auto& x : a)
			x = lower_bound(tmp, tmp + n, x) - tmp + 1;
		for (int i = 1, r; i <= n; i++) {
			r = a[i - 1];
			upd(bit, r, 1);
			wit(i - sum(bit, r - 1));
		}
	}
}

:::

參考資料
---
- [1](https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190)
- [2](https://www.cnblogs.com/dilthey/p/9366491.html?fbclid=IwAR3CCgUAKu9SMhqrYqdH578--hGq1_k0Q9m6I6AMKg4moCOptRD_kP8rSn0)