要求一组数据的 a[l]~a[j] 的和我们可以用前缀和 f[j]-f[i-1]得出，时间复杂度为O(1) 但是如果我们把(l,j)中的一个数修改，例如把a[l]加2 那么如果要维护前缀和数组 要把l~n全部都加2 这样每次修改时间复杂度为O(n) 而如果要把(l,j)的所有数都+2 那么时间复杂度将为 O(n^2) 所以前缀和在面对单点修改和区间修改时效率低下 为了解决数组的单点或者区间更新问题我们引入树状数组
树状数组可以面对的问题方向有：
1.单点修改 （可以单点查询也可以区间查询）
int lowbit(int x){
return x&(-x);
}
int find(int x){
int k=0;
while(x){
k+=c[x];
x-=lowbit(x);
}
return k;
}
int add(int x,int tmp){
while(x<=n){
c[x]+=tmp;
x+=lowbit(x);
}
return 0;
}
int sub(int x,int tmp){
while(x<=n){
c[x]-=tmp;
x+=lowbit(x);
}
return 0;
}2.区间修改
2.a 区间修改+单点查询
方法： 引入差分数组
例如对于下面这个数组
- A[] = 1 2 3 5 6 9
- D[] = 1 1 1 2 1 3
如果我们把[2,5]区间内值加上2，则变成了
- A[] = 1 4 5 7 8 9
- D[] = 1 3 1 2 1 1
只需要修改左区间和右区间边界的值就可以完成区间修改
查询单点时A[i]时A[i] = Σij = 1D[j] 把差分数组D用树状数组表示即可
void update_dot(int idx,int val)//单点更新
{
while(idx <= n)
{
tree[idx] += val;
idx += (idx & -idx);
}
}
void update(int L,int R,int delta)//更新左右端点
{
update_dot(L,delta);
update_dot(R,-delta);
}
void read(int idx)//单点查询
{
int res = 0;
while(idx > 0)
{
res += tree[idx];
idx -= lowbit(idx);
}
return res;
}
2.b 区间修改+区间查询
方法：引入差分数组和辅助数组 通过数学结论得出答案
A[1]+A[2]+...+A[n]
= (D[1]) + (D[1]+D[2]) + ... + (D[1]+D[2]+...+D[n])
= n*D[1] + (n-1)*D[2] +... +D[n]
= n * (D[1]+D[2]+...+D[n]) - (0*D[1]+1*D[2]+...+(n-1)*D[n])
引入辅助数组:sum1[i] = D[i]，sum2[i] = D[i]*(i-1);
void update_dot(int idx,ll delta)
{
for(int i = idx ; i <= n ; i += lowbit(i))
{
tree1[i] += delta;
tree2[i] += (idx-1) * delta;
}
}
void updateRange(int l,int r,ll delta)
{
update_dot(l,delta);
update_dot(r + 1,-delta);
}
ll ask(int idx)
{
ll res = 0;
for(int i = idx ;i > 0;i -=lowbit(i))
res += (idx + 1) * tree1[i] - tree2[i];
return res;
}
ll rangeQuery(int l,int r)
{
return ask(r) - ask(l - 1);
}
3.树状数组求逆序数
方法：单点更新时读入a[i]就add(a[i],1)，求a[i]前面有多少大于a[i]的数==i-find(a[i]) ，但是当面对a[i]很大并且数据分散时，比如只有两个数一个为1，一个为1e12，那么这样做效率也非常低下，所以有时候需要离散化
离散化:引入b[i]数组，将a[i]中的数据映射到b数组中，再int m=unique(b+1,b+1+n)-(b+1)，得到b数组和不重复的数的个数m，再遍历a[i],把a[i]赋值为lower_bound(b+1,b+1+m,a[i])-b，(lower_bound函数返回第一个>=a[i]的数的位置)即a[i]是第几大的数，然后add(a[i],1)即可
C-标枪游戏_第一届河北工业大学程序设计竞赛校赛（同步赛） (nowcoder.com)
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
#define int long long
int c[maxn],a[maxn],b[maxn];
int lowbit(int x){
return x&(-x);
}
int find(int x){
int k=0;
while(x){
k+=c[x];
x-=lowbit(x);
}
return k;
}
int add(int x,int tmp){
while(x<=maxn){
c[x]+=tmp;
x+=lowbit(x);
}
return 0;
}
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
int ans1=0,ans2=0;
int m=unique(b+1,b+1+n)-(b+1);
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+1+m,a[i])-b;
add(a[i],1);
if(i&1){
ans1+=2*find(a[i])-i;
}
else{
ans2+=2*find(a[i])-i;
}
}
//cout<<ans1<<" "<<ans2<<endl;
if(ans1==ans2){
cout<<"hebei shuang king!";
}
else if(ans1>ans2){
cout<<"Calculus is hebei king!";
}
else{
cout<<"huaji is hebei king!";
}
} 4.n维前缀和
题目描述:
给定一段长度为n的序列，求序列中有多少对数相加不会产生10进制的进位。
例如：45 + 54 = 99 不会产生进位，合法。
45 +45 = 90 个位上产生进位，不合法。
0<=n<=2e5 0<=a[i]<1e6
思路:
n维前缀和dp[i][j][k][o][p][q]用来表示小于等于i,j,k,o,p,q的数有多少个，用树状数组维护即可
#include<iostream>
using namespace std;
#define int long long
const int N=2e5+5;
int n,a[N],b[10],cnt[1000100];
int t[11][11][11][11][11][11];
void add(int x,int s)
{
for(int i=1;i<=6;i++) b[i]=x%10,x/=10;
for(int i=1;i<=6;i++) b[i]++;
for(int i=b[1];i<=10;i+=i&-i)
{
for(int j=b[2];j<=10;j+=j&-j)
{
for(int k=b[3];k<=10;k+=k&-k)
{
for(int x=b[4];x<=10;x+=x&-x)
{
for(int y=b[5];y<=10;y+=y&-y)
{
for(int z=b[6];z<=10;z+=z&-z)
{
t[i][j][k][x][y][z]+=s;
}
}
}
}
}
}
}
int query(int b[])
{
int ans=0;
for(int i=b[1];i;i-=i&-i)
{
for(int j=b[2];j;j-=j&-j)
{
for(int k=b[3];k;k-=k&-k)
{
for(int x=b[4];x;x-=x&-x)
{
for(int y=b[5];y;y-=y&-y)
{
for(int z=b[6];z;z-=z&-z)
{
ans+=t[i][j][k][x][y][z];
}
}
}
}
}
}
return ans;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],cnt[a[i]]++;
for(int i=0;i<1000000;i++)
if(cnt[i]) add(i,cnt[i]);
long long ans=0;
for(int i=0;i<1000000;i++)
{
if(!cnt[i]) continue;
bool v=1;
int p=i;
for(int j=1;j<=6;j++)
{
b[j]=p%10,p/=10;
if(b[j]>=5) v=0;
b[j]=10-b[j];
}
ans+=1ll*query(b)*cnt[i];
if(v) ans-=cnt[i];
}
cout<<ans/2;
return 0;
}