樹狀數組:
1.單點修改，區間求和
1.快速求字首和 o(logn)
2.修改某一個數 o(logn)
2.拓展-區間修改，求單點和（結合差分）
3.拓展-區間修改，區間求和
lowbit函數用于取x二進制最低位的1與後面的0組成的數字
原理：二進制的負數是正數取反加一
int lowbit(int x)
{
return t & (-t);
}
原理
假設x = 2ik + 2ik-1 +…+ 2i1
ik >= ik-1 >= … i1
将區間劃分成(左開右閉):
(x - 2i1, x]
包含2i1個數，2i1是右邊界二進制表示的最後一位1與後面的0構成的數
(x - 2i1 - 2i2, x - 2i1]
包含2i2個數，2i2是右邊界二進制表示的最後一位1與後面的0構成的數
(x - 2i1 - 2i2 - 2i3, x - 2i1 - 2i2] …
…
(0, x - 2i1 - 2i2 -…- 2ik-1)
包含2ik個數，包含2ik個數，2ik是右邊界二進制表示的最後一位1與後面的0構成的數
-> 對于其中任意區間 (L,R] 長度是R的二進制表示的最後一位1所對應的數
-> 則對于其中的每一個區間，可以表示為 [R - lowbit(R） + 1, R] (左閉右閉)
-> 可以用數組c[R]表示這個區間總和
-> c[x - lowbit(x) + 1, x] 表示以x為右端點長度為lowbit(x)+1的區間的所有數的和
-> 對于1～x所有數的和，最多可以拆成logx個c[x]的和
樹如圖所示
---------------------------------------------------------------------c16
------------------------------------c8
----------------c4 -------------c12
------c2 ------c6 -----c10 -----c14
-c1 -c3 -c5 -c7 -c9 -c11 -c13 -c15
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
c16 = a16 + c15 + c14 + c12 + c8
10000 01111 01110 01100 01000
tr[i]表示，以i結尾，長度是lowbit(i)的區間内元素的和!!!
求x的子節點
先将x減去1（eg 10000變成01111），每個1對應一個兒子(eg 01111 01110 01100 01000)
c[x] = a[x] + c[x-1] + c[x-1-lowbit(x-1)] + c[x-1-lowbit(x-1)-lowbit(x-2)] +…+ 0
對于x-1-lowbit(x-1)表示将x-1的最後一個一去掉，即實作01111 -> 01110
===========================
代碼實作
1.通過父節點找子節點
對于x-1，有k個兒子，即循環k次，每次減掉最後的1即找到每一個兒子（ eg求字首和）
int sum(int x){
int res = 0;
for ( int i = x; i; i -= lowbit(i) ) tr[x] += tr[i];
return res;
}
2.通過子節點找父節點
更改x的值，即更改(上圖)包含x的所區間
假如x 0011100 -> x父節點p 0100000(唯一的) 0011100 + 0000100 = 0100000
-> p = x + lowbit(x) -> p2 = p + lowbit§ -> p3 = … -> 直到等于n
最多持續logx次（eg某個數加c）
void add(int x, int c){
for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;
}
3.初始化樹狀數組
for ( int i = 1; i <= n; i ++ ) add(i, a[i])
->時間複雜度o(nlogn)
========================================================
例題
1.簡單的整數問題l
區間修改，單點求值
題目
給定長度為 N 的數列 A，然後輸入 M 行操作指令。
C l r d，表示把數列中第 l∼r 個數都加 d
Q x，表示詢問數列中第 x 個數的值
對于每個詢問，輸出一個整數表示答案。
思路
樹狀數組的拓展
将某一區間的每個數加上c，求a[x] -> 差分
将問題變成單點修改，區間求和
樹狀數組中存儲a[i]的差分
構造差分:
b[i] = a[i] - a[i - 1]
代碼
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tr[N], n, m;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;
}
LL sum(int x)
{
LL res = 0;
for ( int i = x; i; i -= lowbit(i) ) res += tr[i];
return res;
}
int main()
{
cin >> n >> m;
for ( int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for ( int i = 1; i <= n; i ++ ) add(i, a[i] - a[i - 1]); //樹狀數組中存a[i]的差分
while ( m -- )
{
char op[2];
scanf("%s", op);
if ( *op == 'C' )
{
int l, r, d;
scanf("%d%d%d", &l, &r, &d);
add(l, d), add(r + 1, -d); //差分日常操作
}
else
{
int x;
scanf("%d",&x);
printf("%lld\n", sum(x)); //差分數組的字首和便是a[i]
}
}
return 0;
}
～～～～～～～～～～～～～～～～～
2.簡單的整數問題ll
（樹狀數組+差分+巧妙運算）區間修改，區間求和**
題目
給定長度為 N 的數列 A，然後輸入 M 行操作指令
C l r d，表示把數列中第 l∼r 個數都加 d
Q l r，表示詢問區間 [l, r] 内元素的和
對于每個詢問，輸出一個整數表示答案。
思路
構造a數組的差分數組b
區間求和：求a1 + a2 +…+ ax (ax = b1 + b2 +…+ bx)
//樸素法(時間複雜度極高)
for ( int i = 1; i <= x; i ++ )
for ( int j =1; j <= i; j ++ )
res += b[j];
//優化法
1.a1到ax的和如圖1）所示，要求圖1）的和，先将圖1）補成圖2）
2)
1) b1 b2 b3 b4 ... bx 注：在沒有b的第0行也要補，補完後是x+1行
b1 b1 b2 b3 b4 ... bx
b1 b2 b1 b2 b3 b4 ... bx
b1 b2 b3 -> b1 b2 b3 b4 ... bx
... ...
b1 b2 b3 b4 ... bx b1 b2 b3 b4 ... bx
2)的求和：(b1 + b2 + ... + bx) * (x + 1)
1)的求和：(b1 + b2 + ... + bx) * (x + 1) - (b1 + 2*b2 + ... + x*bx)
-> 1）的和即為 2)減去i*b的字首和
-> 用tr1維護bi的字首和，tr2維護i*bi的字首和
-> sum(tr1, x) * (x + 1) - sum(tr2, x)
代碼
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL tr1[N], tr2[N];
int a[N], n, m;
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[], int x, LL c)
{
for ( int i = x; i <= n; i += lowbit(i) ) tr[i] += c;
}
LL sum(LL tr[], int x)
{
LL res = 0;
for ( int i = x; i; i -= lowbit(i) ) res += tr[i];
return res;
}
LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}
int main()
{
cin >> n >> m;
for ( int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for ( int i = 1; i <= n; i ++ )
{
add(tr1, i, a[i] - a[i - 1]);
add(tr2, i, (LL)(a[i] - a[i - 1]) * i); //可能會爆int
}
while ( m -- )
{
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if ( *op == 'C' )
{
scanf("%d", &d);
add(tr1, l, d), add(tr2, l, l * d);
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
else printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
return 0;
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)