什么是树状数组呢？
树状数组(Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构 问问度娘吧
在一个线性数组中 ，查询区间和的时间复杂度为O(n)， 修改的时间复杂度为O(1)
这是就会有些机智的孩纸想到了前缀和， 但这样一来，虽节省了查询区间和的时间， 但又使修改的时间复杂度变为了O(n)。
具体实现如下图：
T1单点修改，区间查询
思路
通过树状数组保存并进行修改，利用前缀和求和
#include <cstdio>
const int maxn = 1000005;
long long n, q;
long long a[maxn], BIT[maxn];
int Lowbit(long long x){
return (x & (-x));
}
void Update(long long k, long long x){
a[k] += x;
for(long long i = k; i <= n; i += Lowbit(i)){
BIT[i] += x;
}
}
long long Sum(long long x){
long long ans = 0;
for(long long i = x; i > 0; i -= Lowbit(i)){
ans += BIT[i];
}
return ans;
}
int main() {
scanf("%lld %lld", &n, &q);
for(int i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
Update(i, a[i]);
}
for(int i = 1; i <= q; i ++){
long long x, y, z;
scanf("%lld %lld %lld", &x, &y, &z);
if(x == 1){
Update(y, z);
}
else{
printf("%lld
", Sum(z) - Sum(y - 1));
}
}
return 0;
}
T2 区间修改，单点查询
思路
通过差分组成树状数组，用 sum 求取单点，用 update 更改区间
#include <cstdio>
const int maxn = 1000005;
long long n, m;
long long a[maxn], BIT[maxn];
long long Lowbit(long long x){
return (x & (-x));
}
void Update(long long k, long long x){
for(long long i = k; i <= n; i += Lowbit(i)){
BIT[i] += x;
}
}
long long Sum(long long x){
long long ans = 0;
for(long long i = x; i > 0; i -= Lowbit(i)){
ans += BIT[i];
}
return ans;
}
int main() {
scanf("%lld %lld", &n, &m);
for(long long i = 1; i <= n; i ++){
scanf("%lld", &a[i]);
Update(i, a[i] - a[i - 1]);
}
for(long long i = 1; i <= m; i ++){
long long x, l, r, y;
scanf("%lld", &x);
if(x == 1){
scanf("%lld %lld %lld", &l, &r, &y);
Update(l, y);
Update(r + 1, -y);
}
else{
scanf("%lld", &y);
printf("%lld
", Sum(y));
}
}
return 0;
}
T3 区间修改，区间查询
思路
运用差分求区间修改，通过前缀和查询
推导过程
sum(a[i])
= a[1] + a[2] + a[3] + ......+ a[i - 1] + a[i]
= p[1] + (p[1] + p[2]) +......+(p[1] + p[2] +.....+p[i])
= n * p[1] + (n - 1) * p[2] + .....+ 2 * p[i - 1] + p[i]
= n * (p[1] + p[2] + ...... + p[i]) - (0 * p[1] + 1 * p[2] + .......+(n -1) * p[i])
减号左边 为 BIT1 右边为 BIT2
#include <cstdio>
const int maxn = 1e6 + 5;
int m, n;
int a[maxn];
long long BIT1[maxn], BIT2[maxn];
int Lowbit(int x){
return x & (-x);
}
void Update(int k, int x){
for(int i = k; i <= n; i += Lowbit(i)){
BIT1[i] += x;
BIT2[i] += (long long)(k - 1) * x;
}
}
long long Sum(int x){
long long sum = 0;
for(int i = x; i > 0; i -= Lowbit(i)){
sum += (BIT1[i] * x - BIT2[i]);
}
return sum;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
Update(i, a[i] - a[i - 1]);
}
for(int i = 1; i <= m; i ++){
int flag;
scanf("%d", &flag);
if(flag == 1){
int l, r, x;
scanf("%d %d %d", &l, &r, &x);
Update(l, x);
Update(r + 1, -x);
}
else{
int l, r;
scanf("%d %d", &l, &r);
printf("%lld
", Sum(r) - Sum(l - 1));
}
}
return 0;
}
T4 求逆序对数
思路
用离散化
#include <cstdio>
#include <algorithm>
const int maxn = 1005;
using namespace std;
int n;
int lsh[maxn], a[maxn], BIT[maxn];
int lowbit(int x){
return (x & -x);
}
void Update(int k, int x){
for(int i = k; i <= n; i += lowbit(i)){
BIT[i] += x;
}
}
int sum(int x){
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i)){
ans += BIT[i];
}
return ans;
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
lsh[i] = a[i];
}
sort(lsh + 1, lsh + 1 + n);
int cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1;
for(int i = 1; i <= n; i ++){
a[i] = lower_bound(lsh + 1, lsh + cnt + 1, a[i]) - lsh;
}
long long ans = 0;
for(int i = 1; i <= n; i ++){
Update(a[i], 1);
ans += max(i - sum(a[i]), 0);
}
printf("%lld", ans);
return 0;
}