# BIT & Sparse Table

### 先備知識

* 前綴和 ＆ 差分
* 離散化
* 二分搜

## Sparse Table

### 引入

Sparse Table簡稱ST表或稱為稀疏表，是一個可以用 $O(n \log{n})$時間預處理，$O(1)$回答查詢，解決靜態區間最大最小值問題(RMQ)的資料結構。

### 介紹

ST表基於倍增思想，我們希望能預處理出所有長度為 $2^j$ 區間的答案。實作上通常我們用 $st[i][j]$ 來表示 $[i, i + 2^j - 1]$ 這個區間的答案。因為要處理的區間長度不會超過整個陣列長度，所以我們只需要處理 $st[i][j]$，滿足 $1 \le i \le n, 1 \le 2^j \le n$。如此一來，可能的 $j$ 不會超過 $\lfloor \log_2{n} \rfloor$個，空間複雜度為 $O(n \log n)$

#### 建表
因為區間 $[i, i + 2^j - 1]$ 恰好可以被分成 $[i, i + 2^{j-1} - 1]$ 和 $[i + 2^{j-1}, i + 2^j - 1]$，所以我們可以用類似動態規劃的技巧把ST表建出來。

int st[22][MAXN+5];
// st[0][i] 為原陣列

for (int i = 1; (1<<i) <= n; i++)
    for (int j = 0; j + (1 << i) - 1 <= n; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

:::warning
**注意**
* `f` 函數依照題目所需去調整
* 建表時間複雜度為 $O(n \log n)$
:::

#### 性質
::: info
1. 任何一個長度為 $x$ 的區間可以被拆成最多 $\lceil log_2{x} \rceil$ 個預處理好的區間(即二進位)
2. 任何一個長度為 $x$ 的區間都可以用 $2$ 個預處理好的重疊區間表示
:::

#### 區間和查詢

根據**性質1**，我們可以想到以下的查詢方式。

從大到小枚舉所有 $2$ 的次方，假如現在枚舉到 $2^i$。
如果查詢的範圍 $[L, R]$ 長度大於等於 $2^i$，就將區間 $[L, L + 2^i - 1]$ 的區間和加入答案中，並讓 $L = L + 2^i$繼續枚舉。

int query(int L, int R) {
    long long sum = 0;
    K = __lg(R - L + 1);
    for (int i = K; i >= 0; i--) {
        if ((1 << i) <= R - L + 1) {
            sum += st[i][L];
            L += (1 << i);
        }
    }
    return sum;
}

時間複雜度 $O(K) = O(\log n)$
~~當然，其實這個題目用前綴和就能做了~~

#### 區間極值查詢

上一題之所這麼麻煩是因為我們必須把詢問區間拆成若干個不相交的區間，但如果上面用的函數 `f` 有**可重複貢獻**性質的話，事情就變得簡單了。

:::info
**可重複貢獻性質**
如果函數`f`，滿足`f(x, x) = x`的話，這個函數就滿足可重複貢獻性質，所以像是`max, min, gcd`函數都滿足這個條件，而上面的區間和問題就不滿足這個條件。
:::

那根據我們的**性質2**，我們就可以想到以下的查詢方式(以區間最小值為例)
我們先找到滿足 $2^k\le(R-L+1)$，最大的 $k$，然後我們就可以用 $[L, L+2^k-1]$ 和 $[R - 2 ^ k + 1,R]$ 覆蓋整個區間。

int query(int L, int R) {
    int k = __lg(R - L + 1);
    return min(st[k][L], st[k][R - (1<<k) + 1]);
}

時間複雜度$O(1)$

:::warning
**注意**
使用的取 $log$ 方法不同會大程度影響複雜度
上面用的 `__lg` 是一種很快的方法，因為實作方式是透過位元運算
不建議使用內建數學函數 `log2`，這個非常的慢
另一種可行的做法是預處理，可以參考以下程式碼
::: spoiler code

int lg[MAXN+5];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i/2] + 1;

:::

:::info
**題外話**
ST表在紀錄區間極值的同時，還能順便紀錄極值的位置，如何實作就讓大家回去想想。
:::

### 例題

::: success
[**Codeforces 514D**](https://codeforces.com/problemset/problem/514/D)
有 $n$ 個機器人排成一排，每個機器人都有 $m$ 個裝甲($1$ ~ $m$)和裝甲值($a_1, a_2... a_m$)

現在你有一把雷射槍，每次發射可以選擇一個種類的裝甲 $s \in [1, m]$，並將所有機器人的 $a_s$ 減去 $1$，除非裝甲值已經為 $0$

如果一個機器人的$m$個裝甲值都為 $0$，則稱這個機器人被摧毀。

如果你有 $k$ 次發射機會，並且你可以自行決定發射種類，請給出一種發射方式使得被摧毀機器人的連續區間長度最長。

($1 \le m \le 5, \ 1 \le n \le 10^5, \ 0 \le k \le 10^9$)
:::

::: spoiler Solution
刪除一個區間 $[L, R]$ 的花費即為這個區間每種裝甲的最大值總和。
然後可以發現，固定區間的左端點，當長度越長，需要的花費只會增加，所以很明顯的有單調性，可以二分搜出最右邊的符合條件的右端點。
所以現在的問題就是如何快速的算出一個區間的花費，其實就只要使用 $m$ 個ST表就能輕鬆解決。

時間複雜度 $O(n \log n)$
:::

<br>

:::success
[**Codeforces 475D**](https://codeforces.com/contest/475/problem/D)
給定一個長度為 $n$ 的序列 $a_1, a_2... a_n$ 和 $q$ 筆詢問 $x_1, x_2... x_q$
對於第 $i$ 筆詢問請回答有多少數對 $(l, r)$ 使得 $gcd(a_l, a_{l+1}... a_r) = x_i$
($1 \le n \le 10^5, \ 1 \le q \le 3 \times 10 ^ 5, \ 1 \le a_i, x_i \le 10^9$)
:::

::: spoiler Solution 1
首先我們一樣可以固定左端點，當右端點遞增的時候，整個區間的 $gcd$ 只會變小。
但只有這個結論沒有什麼用，經過更多觀察可以再度發現，如果 $gcd$ 有改變，每次至少變成原本的一半，所以經過 $O(\log A)$ 次後都會變成 $1$ ($A$是左端點上的數值)。
所以我們一樣可以二分搜出每次區間 $gcd$ 出現變化的地方，這樣對於每個左端點最多只需要二分搜 $O(logA)$ 次，每次二分搜可以搭配 ST 表進行區間 $gcd$ 查詢，複雜度 $O(\log {A} \log {n})$
所以總複雜度約為 $O(n \log {n} \log ^ 2 {A})$
:::

:::spoiler Solution 2
我們可以使用掃描線技巧從左到右，當我們掃到第 $i$ 個數時相當於在考慮以 $i$ 為右端點的情況，我們其實可以暴力維護現在出現的所有 $gcd$ 的集合。
因為根據上面的觀察，最多只會有 $1+ \log A$ 個不同的 $gcd$ (加一是因為考慮$gcd$為$1$的情況)。
每次更新只需要把集合裡的所有數拿出來和 $a_i$ 取 $gcd$。
因此複雜度為 $O(n \log^2{A})$
:::

<br>

:::spoiler Code for Solution 1

#include<bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define int long long 
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define ar array
#define mod 1000000007
#define F first
#define S second
#define io ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int mxN = 1e5 + 5;

int n, q, st[mxN][25];
unordered_map<int, int> mp;

void build() {
	for(int i = 0; (1<<i) <= n; i++) {
		for(int j = 0; j + (1<<i) - 1 < n; j++) {
			st[j][i + 1] = __gcd(st[j][i], st[j + (1<<i)][i]);
		}
	}
}

int query(int l, int r) {
	int k = log2(r - l + 1);
	return __gcd(st[l][k], st[r - (1<<k) + 1][k]);
}

int bs(int l, int r, int v) {
	if(l == 0) return 0;
	for(int i = 18; i >= 0; i--) {
		if(l < (1<<i)) continue;
		if(query(l - (1<<i), r) == v) l -= (1<<i);
	}
	return l;
}

void sol() {
	for(int i = 0; i < n; i++) {
		int x = i, g = st[i][0];
		while(x >= 0) {
			int t = x;
			x = bs(x, i, g) - 1;
			mp[g] += (t - x);
			if(x < 0) break;
			g = __gcd(g, st[x][0]);
		}
	}
}

signed main() {
	io;
	cin >> n;
	for(int i = 0; i < n; i++) cin >> st[i][0];
	build();
	sol();
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		cout << mp[x] << '\n';
	}
}

:::

::: spoiler Code for Solution 2

#include<bits/stdc++.h>
#define loli
using namespace std;
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define X first
#define Y second
#define F first
#define S second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(ALL(x), v)
#define ub(x, v) upper_bound(ALL(x), v)
#define re(x) reverse(ALL(x))
#define uni(x) x.resize(unique(ALL(x)) - x.begin())
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define get_bit(x, y) ((x>>y)&1)
#define mkp make_pair
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
#ifdef loli
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

const int mxN = 2e6 + 5;

inline void solve() {
    int n, q; cin >> n;

    map<int, int> mp, ans;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        map<int, int> tmp;

        for (auto &p : mp) 
            tmp[__gcd(p.first, a)] += p.second;

        tmp[a]++;
        
        for (auto p : tmp) 
            ans[p.first] += p.second; 

        swap(mp, tmp); 
    }
    
    cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << ans[x] << '\n';
    }
}

signed main() {
	IO;	
	solve();	
}

:::

### 練習題

[TOIJ 1603](https://tioj.ck.tp.edu.tw/problems/1603)

[Coprime Segment](https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/G)

### 總結

ST表的使用時機通常會在查詢次數比較大且不需要修改時。
ST表做區間極值查詢的複雜度是$O(1)$，做區間$gcd$的複雜度是$O(logA)$。
而線段樹做區間極值查詢的複雜度是$O(logn)$，做區間$gcd$複雜度是$O(logA + log n)$(這部分可以稍微自己思考一下)。
所以相對於線段樹來說，ST表還是一個相當輕量化而且比較快速的資料結構。

## BIT (Fenwick Tree)

### 引入
BIT(binary index tree)中文譯做樹狀數組，是一個用來維護前綴訊息的資料結構。

其實，BIT能解決的問題用線段樹也都能解決，但因為程式碼很短，時間效率很高而被廣大競程選手喜愛。

### 介紹

BIT最常見的應用就是拿來維護前綴和，下面我們就用前綴和來做介紹。

BIT能很輕鬆的在$O(\log n)$的時間內做到單點查詢和修改。

我們先用下面這張圖來理解一下，$c[i]$ 是我們的樹狀數組，$a[i]$是原陣列。


$c[i]$ 存的資訊都是一個連續區間的和，乍看之下沒有什麼規律

$c[2]$ 存 $a[1...2]$
$c[4]$ 存 $a[1...4]$
$c[6]$ 存 $a[5...6]$
$c[8]$ 存 $a[1...8]$
剩下的 $c[x]$ 存 $a[x]$

可能只能看出 $c[x]$ 存的區間右端點也會是 $x$
那左區間究境要怎麼找呢，這時候我們需要換成二進位來看看

$c[10]$ 存 $a[01...10]$
$c[100]$ 存 $a[001...100]$
$c[110]$ 存 $a[101...110]$
$c[1000]$ 存 $a[0001...1000]$

現在我們要先說一個東西叫做lowbit，也就是二進位中最低位的那個 $1$
這樣我們就可以發現 $c[i]$ 儲存的區間就是 $[i - lowbit(i) + 1, i]$
~~不要問我怎麼看出來的~~

:::info
**lowbit小學堂**
在C++中，`-x`的二進位表示會是`x`取補數後加一
所以如果 `x` 是 `101100`
那麼 `-x` 就會是 `010011` 再加一，也就是 `010100`
所以只要使用 `x&(-x)` 就可以找到 `x` 的 lowbit 了！
:::

### 區間查詢

知道 $c[i]$ 的儲存區間後，我們就可以來試試看區間查詢了。

::: info
**小提醒**
因為BIT只能查詢前綴，所以如果要查詢區間 $[L, R]$ 時，通常會用到差分技巧，也就是用前綴 $[1, R]$ 扣掉 $[1, L-1]$ 來得到區間 $[L, R]$
:::

假如我們現在要查詢前綴 $[1, x]$，我們就可以從 $c[x]$ 開始

$c[x]$ 存了 $[x-lowbit(x) + 1, x]$

所以我們考慮完 $c[x]$ 的貢獻後，接著只需要考慮 $[1, x - lowbit(x)]$

接著我們只需要重複以上步驟，持續將 $c[右端點]$ 加入答案中，並縮小查詢區間，直到查詢右端點變為 $0$ 就代表查詢結束。

#define lowbit(x) (x&(-x))
int getsum(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

這樣時間複雜度會是$O(K)$, $K$是查詢數字二進位表示中的 $1$ 的數量
所以 $K = O(\log x)$

### 單點修改

修改的部分就比較難懂了，因為我們如果要修改 $x$，就必須找出所有有覆蓋到 $x$ 的 $c[i]$。

首先很明顯只有 $\ge x$ 的點會覆蓋到 $x$
所以只要找到滿足 $i - lowbit(i) \le x \le i$ 的 $i$ 就好

根據一些精闢觀察，可以發現 $i$ 必須滿足以下條件。

* $x \le i$
* $lowbit(x) \le lowbit(i)$
* $i$ 的 $lowbit(i)$ 之上的位數會和 $x$ 一樣

所以我們可以用以下構造方式找出所有符合條件的 $i$

void add(int x, int k) {
  while (x <= n) {  // 不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

如果這個部分不是很了解也沒關係，~~因為我自己也不太了解~~

### TIB

如果很不小心的你將BIT的查詢和修改操作寫反了
像這樣(以維護區間和為例)

void modify(int x, int v) {
    for (int i = x; i > 0; i -= lowbit(i)) 
        bit[i] += v;
}

int query(int x) {
    int res = 0;
    for (int i = x; i <= n; i += lowbit(i)) 
        res += bit[i];
    return res;
}

那你維護的東西就會從前綴變成後綴XD

### BIT上二分

這邊提供一個 BIT 的有趣技巧
如果我們想找到 BIT 上第一個大於等於 $k$ 的位置

實作上我們會先找到小於 $k$ 的最後一個位置，然後再 $+1$，這樣會比較好做

那我們可以直接透過二分搜達到此效果

int findk(int k) {
    int l = 1, r = n;
    while (l < r) {
        int mid = (l+r) / 2;
        if (bit.qry(mid) < k) l = mid;
        else r = mid - 1;
    }
    return l + 1;
}

複雜度 $O(\log^2{n})$

但其實有一個更好的做法，就是直接在BIT上二分搜(倍增)，複雜度是好好的 $O(\log n)$

我們從最長的區間開始搜尋

如果這個區間的答案 < $k$，我們就將這個區間的答案加入，並且往右下繼續搜尋

如果這個區間的答案 $\ge k$，我們就直接往左下搜尋

實做詳情可以參考下面的圖表和程式碼


int findk(int k) {
    int id = 0, res = 0;
    int mx = __lg(n) + 1;
    for (int i = mx; i >= 0; i--) {
        if ((id | (1<<i)) > n) continue;
        if (res + b[id|(1<<i)] < k) { 
            id = (id | (1<<i));
            res += b[id];
        }
    }
    return id + 1;
}

### O(N) 建BIT
以維護區間和為例

#### 方法 1
可以觀察上面的樹狀結構圖，可以發現每個節點所代表的值就是他所有子節點的值總和。
所以我們可以從下往上更新，每計算完一個節點就將他的值貢獻到父節點。

for (int i = 1; i <= n; ++i) {
    bit[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) bit[j] += bit[i];
}

#### 方法 2
既然我們已經知道 `bit[i]` 所代表的範圍，那就可以很輕鬆的用前綴和來快速算出這個區間的答案。(前提是維護的東西能在 $O(1)$ 被查詢出來)

for (int i = 1; i <= n; ++i) {
    bit[i] = prefix_sum[i] - prefix_sum[i - lowbit(i)];
    // bit[i] -> [i - lowbit(i) + 1, i]
}

### 例題

:::success
[**Static Range Minimum Queries**](https://cses.fi/problemset/task/1647)
靜態區間最小值查詢
:::

:::spoiler Solution
這題有千千百百種作法，但是要用BIT做還真的有一點難。
由於我們目前學的BIT只能維護前綴訊息，所以如果我們只有能前綴$min$的話要如何做這題呢？

沒錯！就是離線處理，我們希望透過離線處理，當我們要查詢區間 $[L, R]$時，不會被 $[1, L-1]$ 的數字影響到，這樣一來我們就可以直接查詢 $[1, R]$ 的前綴 $min$

所以我們其實只需要將詢問按照左端點由大到小排序，每此詢問時確保 $L$ 和 $L$ 之後的數都被加入BIT中，$L$ 之前的數都還沒(設成無限大)

:::

:::spoiler Code

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long 
#define lowbit(x) (x&-x)
 
const int maxn = 2e5;
using namespace std;
 
struct qu{
	int s,e,id;	
	bool operator < (qu a){
		return s > a.s;
	}
};
 
int n,q,bit[maxn+10],x[maxn+10],ans[maxn+10];
vector<qu> v;
 
int query(int x){
	int ans = 1e10;
	for(int i = x; i > 0; i -= lowbit(i))
		ans = min(ans,bit[i]);
	return ans;
}
 
void modify(int x,int v){
	for(int i = x; i <= n; i += lowbit(i))
		bit[i] = min(bit[i],v);
}
 
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	memset(bit,63,sizeof bit); //初始化為無限大
	for(int i = 1; i <= n; i++)
		cin >> x[i];
	int a,b,cnt = 0, z= q;
	while(z--){
		cin >> a >> b;
		v.pb({a,b,cnt++});
	}
	sort(all(v));
	
	for(int i = 0, j = n;  i < v.size() ; i++){
		while(j > 0 and j >= v[i].s){
			modify(j,x[j]);
			j--;
		}
		ans[v[i].id] = query(v[i].e);
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

:::

<br>

:::warning
注意！
用BIT維護前綴 $min$ 時，單點修改並不是真正的單點改值。
比如說 `modify(pos, val)`，其實只是將在區間 $[1, pos]$ 裡的數都和 $val$ 取 $min$ 而已

:::

<br>

:::success
[**Distinct Values Queries**](https://cses.fi/problemset/task/1734)
給一個數列和一堆區間查詢，每次要回答區間內有多少相異元素個數。
:::

::: spoiler Solution
~~經典到不能再經典的題目，相信大家都已經會了。~~
:::

<br>

:::success
[**Josephus Problem II**](https://cses.fi/problemset/task/2163/)
$n$ 個學生，照編號 $1$ ~ $n$ 圍成一圈，並進行一個遊戲。遊戲中每輪將跳過 $k$ 個學生後，把目前指到的學生從圓圈中移除，直到所有的學生都被移除，請依序輸出被移除的學生編號。
:::

::: spoiler Solution
如果 $a[i] = 1$ 代表第 $i$ 個人還活著，$a[i] = 0$ 則代表第 $i$ 個人已經死了。
接下來用BIT維護，我們只需要支援將一個人刪除和查詢場上第 $x$ 個還存活的人，這就可以用上面所提到的BIT上二分。

最後小心處理環狀就好。
:::

<br>

:::success
[**Dominant Free Sets**](https://csacademy.com/contest/archive/task/dominant-free-sets/statement/)
給你二維平面上的 $n$ 個點，如果 $x_A \ge x_B$ 且 $y_A \ge y_B$ 則點$A(x_A, y_A)$ 覆蓋點$B(x_B, y_B)$。

請問在這 $n$ 個點的所有子集中，有多少子集滿足任兩點都不存在覆蓋關係。
:::

::: spoiler Solution
其實這是一個很經典的問題被稍微包裝了一下。
如果有自己畫圖看過的話，應該不難發現如果選出來的點兩兩都不存在覆蓋關係，那一定會是隨著 $x$ 座標增加 $y$ 座標就會遞減的。

那這題就變成了一個經典DP問題(求遞增(減)子序列數量)

所以我們先把所有點按照 $x$ 排序由小到大排序，並進行以下DP

$dp[h]$ 代表結尾高度是 $h$ 的遞減子序列數量

當我們掃到點 $(x_i, y_i)$ 時，我們可以如此轉移

$dp[y_i] = dp[y_i] + 1 + \sum_{k = y_i+1}^{MAXY} dp[k]$

$+1$ 是因為可以將這個點自己一人一組，也是一個合法的選法

或是可以從結尾高度大於 $y_i$ 的序列進行轉移

$x$ 座標相同的點要如何處理需要稍微小心

:::

::: spoiler Code

#include<bits/stdc++.h>
#define loli
using namespace std;
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define X first
#define Y second
#define F first
#define S second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define eb emplace_back
#define push emplace
#define lb(x, v) lower_bound(ALL(x), v)
#define ub(x, v) upper_bound(ALL(x), v)
#define re(x) reverse(ALL(x))
#define uni(x) x.resize(unique(ALL(x)) - x.begin())
#define inf 1000000000
#define INF 1000000000000000000
#define mod 1000000007
#define get_bit(x, y) ((x>>y)&1)
#define mkp make_pair
#define IO ios_base::sync_with_stdio(0); cin.tie(0);
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
#ifdef loli
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

const int mxN = 2e5 + 5;

int n;
pii pt[mxN];

int bit[mxN];

void upd(int i, int val) {
    for (; i > 0; i -= (i&-i)) {
        bit[i] += val;
        if (bit[i] >= mod) bit[i] -= mod;
    }
}

int qry(int i) {
    int res = 0;
    for (; i <= 100000; i += (i&-i)) {
        res += bit[i];
        if (res >= mod) res -= mod;
    }
    return res;
}

inline void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> pt[i];
    sort(pt, pt + n, [](pii a, pii b) {
        if (a.X == b.X) return a.Y < b.Y;
        return a.X < b.X;
    });
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int res = 1 + qry(pt[i].Y + 1); 
        ans = (ans + res) % mod;
        upd(pt[i].Y, res);
    }
    cout << ans << '\n';
}

signed main() {
	IO;	
	solve();	
}

:::

### 練習題

[【模板】树状数组 2](https://www.luogu.com.cn/problem/P3368)

[Increasing Array Queries](https://cses.fi/problemset/task/2416)

### 總結

BIT是一非常神奇的資料結構，要完全弄懂他是如運作的真的有點困難。
BIT其實還能做到區間加值區間查詢、在線RMQ並且支援修改等很多神奇的應用，但因相較於線段樹來說比較不直觀，所以比較少人去使用。所以建議大家先把BIT基礎的用法搞熟，再去研究這些額外的技巧。

想研究更多BIT用法的人可以參考:
[Efficient Range Minimum Queries using Binary Indexed Trees](http://history.ioinformatics.org/oi/files/volume9.pdf#page=41)
[OI wiki 樹狀數組](https://oi-wiki.org/ds/fenwick/#%E5%BC%95%E5%85%A5)