---
tags: 109_FDCS
---

# Binary Indexed Tree (Fenwick tree)
又稱樹狀數組, 樹狀陣列, 二元索引樹

用來快速求帶修改的區間和
修改、查詢操作都是 $O(lgn)$
刻起來比線段樹快而且常數比較小(空間甚至只要 $O(n)$ )
但區間修改+區間查詢的實現比較不直覺，要用奇怪的功能盡量用線段樹

---

## 操作
- 單點修改&區間查詢
- 區間修改&單點查詢

---

## 概念

利用位元的概念把可以把一個前綴和拆成數個數字的加總

以下是在 $n=8$ 時，BIT的示意圖


其中**黑色實線是查詢用的順序**、**紅色虛線是修改用的順序**

### 查詢(前綴和)

對某一個點進行查詢時，沿著**黑色實線**走到 $0$ ，把路過的點值都加總就是所求

### 修改

對某一點進行修改時，沿著**紅色虛線**走到不能走為止( $\leq n$ )，對路過的點進行修改

---

為什麼和位元有關係呢

必須先知道**lowbit**是什麼

### lowbit

lowbit是方便接下來操作要用的一個輔助函式
功能是取得一個整數中最低位的 $1$ 所代表的值

e.g.

整數 $21_{(10)}=10101_{(2)}$
$lowbit(21)=1$ ，因為最低位的 $1$ 是最右邊的那個 $1$ ，而那個位置代表的是 $1$

另一個例子
整數 $20_{(10)}=10100_{(2)}$
$lowbit(20)=4$ ，因為最低位的 $1$ 是右邊數來第三個 $1$ ，而那個位置代表的值是 $4$

---

知道了lowbit之後
把上面的圖裡的數字用二進位表示的話


可以看出
黑色實線對應的是**減去該點的lowbit**
紅色虛線對應的是**加上該點的lowbit**

---

那為什麼前綴和會是對的呢，不會有重複取到同樣範圍的問題嗎?

對於這個問題我們可以看第三個圖
這次我們把節點的內容換成所代表的區間


很像砍掉一半的線段樹，實際上概念差不多
知道理論之後就可以來實作了

---

## 實作

### 單點修改&區間查詢

先開一個大小為 $n+1$ 的陣列

constexpr int maxn = 1e5;
long long BIT[maxn + 1];

#### lowbit輔助函式

小技巧，背起來即可 :poop:

inline int lowbit(int x) {return x&-x;}

#### 修改

對 $p$ 的位置加上 $x$

**注意**
**BIT實作的時候是1-based，換句話說陣列是從1開始**
如果`p`是0-based的話要調整一下

void modify(int p, long long x) {
    p++;
    while(p <= maxn)
        BIT[p] += x, p += lowbit(p);
}

#### 查詢

查詢 $0$ 到 $p$ 的前綴和

long long prefix(int p) {
    long long ret = 0;
    p++;
    while(p)
        ret += BIT[p], p -= lowbit(p);
    return ret;
}

---

### 區間修改&單點查值

把陣列存的值改成差分就好了，自己想 :poop:

---

## 例題 [a164: 0927進階班作業-區間和](http://203.64.191.163/ShowProblem?problemid=a164)

constexpr int maxn = 2e5 + 5;
using ll = long long;
ll bit[maxn];
int n = 0, k, l, r, q;
inline int lowbit(int p) {return p & -p;}

inline ll prefix(int p) {
	ll ret = 0;
	while (p)
		ret += bit[p], p -= lowbit(p);
	return ret;
};

inline void modify(int p, ll x) {
	while (p < maxn)
		bit[p] += x, p += lowbit(p);
};

inline ll query(int l, int r) {
	return prefix(r) - prefix(l - 1);
};

inline void solve() {
	string str; getline(cin, str);
	stringstream ss(str);
	while (ss >> k) modify(++n, k);
	cin >> q; while (q--)
		cin >> l >> r, cout << query(min(l, r), max(l, r)) << endl;
}

<!--
:::spoiler CPP RANK 1(2020/12/16) 毒瘤IO優化 BIT code

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>

#if __cplusplus > 201703L
#include<concepts>
#endif

using namespace std;

#define debug(x) cout << #x << " : " << x << endl

namespace abb {
using ll = long long;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
}

namespace output {
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (const auto& i : v) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
	for (const auto& i : s) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
	for (const auto& i : m) os << i << ' ';
	return os;
}
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}


//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

#define eb emplace_back

inline void init() {

}

constexpr int maxn = 200005;

ll bit[maxn];
int n = 0, k, l, r, q;
inline int lowbit(int p) {return p & -p;}

inline ll prefix(int p) {
	ll ret = 0;
	while (p)
		ret += bit[p], p -= lowbit(p);
	return ret;
};

inline void modify(int p, ll x) {
	while (p < maxn)
		bit[p] += x, p += lowbit(p);
};

inline ll query(int l, int r) {
	return prefix(r) - prefix(l - 1);
};

inline void solve() {
	string str;
	while (cin.rdbuf()->sgetc() != '\n') {
		n += cin.rdbuf()->sgetc() == ' ';
		str += cin.rdbuf()->sbumpc();
	}
	auto tmp = cin.rdbuf();
	stringstream ss(str);
	cin.rdbuf(ss.rdbuf());
	for (int i = 0; i <= n; i++)
		fin >> k, modify(i + 1, k);
	cin.rdbuf(tmp);
	fin >> q; while (q--)
		fin >> l >> r, fout << query(min(l, r), max(l, r)) << endl;
}

//#define FILEIO
main() {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein("in.txt", ios::in);
	fstream fileout("out.txt", ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t;
#endif
	while (t--) solve();
	return 0;
}

:::
-->