Binary Indexed Tree(BIT)
===
###### tags: `Algorithm`

## 詳解
我們知道我們可以利用前綴和來處理區間和, 而 BIT 是一種高效處理前綴和的資料結構

如何儲存前綴和呢?

對於 1~n 的整段合起來的資料,不斷的往下儲存左半邊.
可以發現剛好有空位放下全部的區段

如此 `a1+...+a7` 我們可以表示成 `BIT[111] + BIT[110] +　BIT[100]`

可以觀察到, 當我們減去位置 n 的 lowbit, 就能得到上一層
重複動作, 能找出所有組成位置 n 的區塊

int sum( int n)
{
	int s=0;
	while(n>0)
	{
		s += BIT[n];
		n-=lowbit(x); 
	}
	return s;
}

得到前綴和後, 就可以查詢區間資料了

int query( int a, int b)
{
	if(a>b) swap(a,b);
	return sum(b)-sum(a-1);
}

單點修改

void add( int i, int x)
{
    for( int j=i; j<=maxN; j+=lowbit(x))
    {
        BIT[j] += x;
    }
}

## 提示

* BIT index 從1開始, 兩邊閉區間
* lowbit
* `(x&-x)`
* 修改
* 一直往後找下層`( j+=lowbit(j) )`
* 查詢前綴
* 一直往前找上層`( j-=lowbit(j))`

## Code

#define lowbit(x) (x&-x)
#define maxN 10000

long long BIT[maxN];

inline long long sum( int i)
{
    long long s = 0;
    for( int j=i; j>0; j+=lowbit(j))
    {
        s+=BIT[j];
    }
    return s;
}

inline void add( int i, int x)
{
    for( int j=i; j<=maxN; j+=lowbit(j))
    {
        BIT[j]+=x;
    }
}

inline long long query( int l, int r)
{
    if(l>r) swap(l,r);
    return sum(r)-sum(l-1);
}

# 區間修改, 區間查詢 BIT
[ref](https://www.cnblogs.com/dilthey/p/9366491.html)

了解區間修改, 區間查詢要先了解一個看起來沒什麼用的東西: **區間修改, 單點查詢**
## 區間修改, 單點查詢

原始陣列為 a
差分陣列為 d

d[i] = a[i]-a[i-1]
d[1] = a[1]

#### 修改
`a[L:R]` 全部 + x
但只有 `d[L]` 和 `d[R+1]` 有變化:
`d[L]` 增加 x
`d[R+1]` 減少 x

#### 查詢
`a[pos] = (a[１])+(-a[1]+a[2])+(-a[2]+a[3])+....+(-a[pos-1]+a[pos])`
則 `a[pos] = d[1]+...+d[pos]`

***因此, 我們可以用 bit 來維護 d 並且支援上面兩個操作***

// binary index tree
int tr[N], n;
inline void add (int p, int x)
{
	for (int i=p; i<=n; i+=lowbit(i)) tr[i] += x;
}
inline int sum (int p)
{
	int res = 0;
	for (int i=p; i>0; i-=lowbit(i)) res += tr[i];
	return res;
}

// query, range base add
inline void radd (int l, int r, int x)
{
	add(l,x), add(r+1,-x);
}
inline int query (int p)
{
	return sum(p);
}

## 區間修改, 區間查詢

m[i] = d[i]*i

#### 區間查詢

要實現 a的區間查詢顯然需要基於 a 的前綴和

sum[n]
= a[1]+...+a[n]
= d[1] +　d[1]+d[2] +　d[1]+...+d[n]
= d[1]*(n) +　d[2]*(n-1) + ... + d[n]*1
= (d[1]+...+d[n])*(n+1) - (m[1]+...+m[n]);

#### 區間修改

a[L:R]+x ->
d[L]+x, d[R+1]-x ->
(m[L]) + x*L, m[R+1] - x*(R+1)

:::info
可以用前綴和查詢原始序列
用 bit 維護修改
把原始前綴和加上修改就是答案
這種做法可以把 build 從 O(nlogn) 降到 O(n)
:::

***一樣用 bit 維護 m***

int tr[N], tr2[N], n;
inline void add (int p, int x) // 外面不能呼叫, 他修改的是 d 和 m, 並非 a(原始序列)
{
	for (int i=p; i<=n; i+=lowbit(i)) tr[i] += x, tr2[i] += x*p;
}
inline int sum (int p) // a 前綴
{
	int res = 0;
	for (int i=p; i>0; i-=lowbit(i)) res += tr[i]*(p+1) - tr2[i];
	return res;
}

inline void radd (int l, int r, int x) // 修改 a
{
	add(l,x), add(r+1,-x);
}
inline int query (int l, int r)
{
	return sum(r) - sum(l-1);
}