int bit[MAXN]; //存BIT節點的陣列
int query(int i){
int res = 0;
while(i){ //當i不等於零時，去找答案
res += bit[i]; //更新答案
i -= i&(-i); //減掉lowbit，繼續找答案
}
return res;
}
這樣就完成前綴詢問了！
單點修改
那如果我們要進行單點修改呢？只要更新會用到這個點的區間不就好了！
因此，要做單點修改時，我們持續去更新那些值就好了！
void update(int i, int val){
while(i < MAXN){ //當i小於陣列大小時，去更新答案
bit[i] += val; //更新答案
i += i&(-i); //加上lowbit，繼續更新答案
}
}
應用
所以說，詢問與操作前綴有什麼用呢？這裡舉幾個例子
逆序對
因此，我們每次加入數字時，就可以去找有幾個數字比當前的數字大
如下：
int ans = 0;
for(int i = 0; i < n; i++){
//在答案增加在這個元素前有幾個更大的數字
ans += query(MAXN-1)-query(arr[i]);
//更新樹上的資料
update(arr[i]);
}
或可以將陣列倒過來做，就不用每次都做兩次詢問了
int ans = 0;
for(int i = n-1; i >= 0; i--){
//在答案增加在這個元素後面有幾個更小的數字
ans += query(arr[i]-1);
//更新樹上的資料
update(arr[i]);
}
最長遞增子序列（LIS, Longest Increasing Subsequence）
但這裡也可以用 BIT 去做到同樣的事情，但要換成維護前綴最大值
int query(int i){
int res = 0;
while(i){ //當i不等於零時，去找答案
res = max(res, bit[i]); //更新答案
i -= i&(-i); //減掉lowbit，繼續找答案
}
return res;
}
void update(int i, int val){
while(i < MAXN){
bit[i] = max(bit[i], val);
i += i&(-i);
}
}
而作法如下：
int dp[n];
for(int i = 0; i < n; i++){
//找前面比自己小的數字最長的子序列長度+1
dp[i] = max(query(arr[i])+1, dp[i]);
update(arr[i], dp[i]); //更新答案
}
BIT 上二分搜
要在 BIT 上二分搜，有兩種方法，而這裡我們用一個例題來講述
而寫法分為兩種，一種是正常二分搜，第二種是倍增法二分搜
//正常二分搜
int find(int k){
int l = 0, r = n;
while(l < r){
int m = (l+r)/2;
if(query(m) >= k) r = m;
else l = m+1;
}
}
//l即為第k大的元素
//倍增法二分搜
int find(int k){
int sum = 0, pos = 0;
for(int i = LOGN; i >= 0; i--)
if(pos + (1<<i) < n && sum + bit[pos + (1<<i)] < k){
sum += bit[pos + (1<<i)];
pos += (1<<i);
}
}
return pos;
}
練習題
單點修改、區間詢問
第一、二題：區間求和線段樹
#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAXN = 1e5+5;
ll bit[MAXN];
void update(int i, ll val){
while(i < MAXN){
bit[i] += val;
i += i&(-i);
}
}
ll query(int i){
ll res = 0;
while(i){
res += bit[i];
i -= i&(-i);
}
return res;
}
signed main(){
fastio
int n, m;
cin >> n >> m;
ll arr[n+1];
for(int i = 1; i <= n; i++) cin >> arr[i];
for(int i = 1; i <= n; i++) update(i,arr[i]);
for(int i = 0; i < m; i++){
int op;
cin >> op;
if(op == 1){
ll i,v;
cin >> i >> v;
i++;
update(i,-arr[i]);
arr[i] = v;
update(i,arr[i]);
}else if(op == 2){
int l, r;
cin >> l >> r;
l++;
cout << query(r) - query(l-1) << "\n";
}
}
}
逆序對
給一個陣列，問在每個點前面有幾個比他大的數字
#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5+5;
int bit[N];
void update(int pos, int val){
while(pos<N){
bit[pos] += val;
pos += pos&-pos;
}
}
int query(int pos){
int res = 0;
while(pos){
res += bit[pos];
pos -= pos&-pos;
}
return res;
}
signed main(){
fastio
int n;
cin >> n;
while(n--){
int x;
cin >> x;
cout << query(N-1) - query(x) << " ";
update(x,1);
}
}
LIS(DP)
今天你希望由左到右選取一些高度遞增的花
問最大的漂亮程度總和為？
#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5+5;
ll h[N], a[N], bit[N];
void update(int i, int v){
while(i < N){
bit[i] = max(bit[i],v);
i += i&-i;
}
}
int query(int i){
int ans = 0;
while(i){
ans = max(ans,bit[i]);
i -= i&-i;
}
return ans;
}
signed main(){
fastio
int n;
cin >> n;
for(int i = 0;i < n;i++) cin >> h[i];
for(int i = 0;i < n;i++) cin >> a[i];
for(int i = 0;i < n;i++){
update(h[i],query(h[i])+a[i]);
}
cout << query(n) << "\n";
}
