E - 樹狀陣列 1

原題連結

題意

已知一個數列，你需要進行下面兩種操作：

將某一個數加上 $x$
求出某區間每一個數的和

lowbit函數

定義一個函數$f=lowbit(x)$，這個函數的值是$x$的二進位制表示式中只保留最低位$1$得到的十進位制數

比如:

\[(6)_{10}=(110)_2 \]

那麼$lowbit(6)$就等於$2$，因為$(110)_2$中最低位（就是從右往左數的第二位）對應的數是$(10)_2=(2)_{10}$

所以假設一個數的二進位制最低位的1在從右往左數的第k位，那麼它的lowbit值就是

\[2^{k−1} \]

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

原理：
根據計算機二補數的性質。
二補數就是原碼的反碼加一
如：

\[(110)_2=(6)_{10} \]

反碼：

\[(001)_2 \]

加一：

\[(010)_2 \]

可以發現變為反碼後 x 與反碼數位位每一位都不同，當反碼加1，反碼會逢1一直進位直到遇到0，且這個0變成了1，所以這個數最後面構造了一個 100… 串。只有一個$1$,因此進行&運算後除了該位上存在$1$，其他位都是$0$（反碼的最低位$0$變成$1$，與反碼取反前的原碼相同都是$1$）,進而得到二進位制表示式中只保留最低位$1$得到的十進位制數

樹狀陣列的定義

樹狀陣列是一種維護字首和的資料結構，可以實現 $O(\log{n})$查詢一個字首的和，$O(\log{n})$對原數列的一個位置進行修改。

與字首和相同的是，樹狀陣列使用與原數列大小相同的陣列即可維護
與字首和不同的是，樹狀陣列的一個位置 i 儲存的是從 i 開始，（包括 i）向前$t_i$個元素的和
$t_i$就是最大的可以整除 $i$ 的$2$的冪（通過上述$lowbit$函數可以得到）

樹狀陣列的性質

設樹狀陣列為b
性質1：有上述定義得到$b[k] = \sum_{k-lowbit(k)+1}^{k} $
性質2：父節點 $b[dad] = b[k] + lowbit(k)$

(上為樹狀陣列b,下為原陣列a)

樹狀陣列單點修改

根據性質2可以改造出對樹狀陣列單點修改的函數
$add(int \ k,int \ x)$功能：下標為k的增加x

void add(int k,int x){
	while(k <= n){	//不能超範圍
		b[k] += x;
		k += lowbit(k);	//維護父節點
	}
}

注意：空陣列本身就是一個樹狀陣列(和均為0),因此原陣列輸入資料維護樹狀陣列b時可以直接$add(i,a_i)$

樹狀陣列區間查詢

作差求l_{r的區間和:sum[1}r] - sum[1~l-1]
根據性質1：

LL getsum(int l,int r){		
	l --;
	LL s1 = 0;
	while(l){
		s1 += b[l];
		l -= lowbit(l);
	}
	LL s2 = 0;
	while(r){
		s2 += b[r];
		r -= lowbit(r);
	}
	return s2 - s1;
}

最終程式碼

點選檢視程式碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;

#define X first
#define Y second

typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e6+10;
const int M = 2e5+10;
int n,m;
int a,b[N];

int lowbit(int x){
	return x & -x;
}
void add(int k,int x){
	while(k <= n){
		b[k] += x;
		k += lowbit(k);
	}
}
LL getsum(int l,int r){
	l --;
	LL s1 = 0;
	while(l){
		s1 += b[l];
		l -= lowbit(l);
	}
	LL s2 = 0;
	while(r){
		s2 += b[r];
		r -= lowbit(r);
	}
	return s2 - s1;
} 

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ){
		cin >> a;
		add(i,a);
	}
	while(m -- ){
		int op;
		cin >> op;
		if(op == 1){
			int k,x;
			cin >> k >> x;
			add(k,x);
		}
		else{
			int l,r;
			cin >> l >> r;
			cout << getsum(l,r) << nl;
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);

	solve();
}