题目描述
blablabla
样例
blablabla
下面这段代码的基本功能是:
已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数,表示一个操作,具体如下:
操作1: 格式:1 x k 含义:将第x个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
查询操作的时间复杂度为O(logn)
C++ 基本的树状数组模板代码
#include<iostream>
#define MAXN 2000010
using namespace std;
int n,m,a;
int q,x,y;
int e[MAXN];//树状数组,树状数组index是从1开始的
int lb(int o){ //lowbit
return o&(-o);
}
void addto(int x,int v){
while(x<=n){
e[x]+=v;
x+=lb(x);
}
}
int query(int x){
int ans=0;//因为e[i]中有a[i],所以ans从0开始加
while(x>0){
ans+=e[x];
x-=lb(x);
}
return ans;
}
int main(){
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&a);
addto(i,a);
}
for(i=1;i<=m;i++){
scanf("%d%d%d",&q,&x,&y);
if(q==1) addto(x,y);
else printf("%d\n",query(y)-query(x-1));
}
return 0;
}
交换次数等价于i< j, ai> aj 的个数(逆序对),如果对于每一个j我们都能快速求出有多少对那么问题就能解决了。
首先我们对数组离散化。数组内的值应为没有重复值,离散化后每个数值都是等于第几大的数。
我们构建一个1-n的树状数组,按照j=1,2,…n的顺序进行如下操作:
1.把j-(树状树状中查到前aj项的和)加入答案中。
2.把树状树状的aj位置的值加1
对于每一个j,(树状数组查询的前aj项的和)就是满足i< j, ai< aj的i个数。所以这个值从j中减去后就是满足i< j, ai> aj的i个数。对于每个j的复杂度是O(logn),所以整个查询是O(nlogn)。
C++ 代码
int n,m,e[1024];
int lb(int o){ //lowbit
return o&(-o);
}
void addto(int x,int v){
while(x<=n){
e[x]+=v;
x+=lb(x);
}
}
int query(int x){
int ans=0;//因为e[i]中有a[i],所以ans从0开始加
while(x>0){
ans+=e[x];
x-=lb(x);
}
return ans;
}
int inversePairs(vector<int>& nums) {
int i,res=0;
n=nums.size();
int t[n+1];
int a[n+1];
for(int i=1;i<=n;i++){
a[i]=nums[i-1];
t[i]=a[i];
}
sort(t+1,t+n+1);
m=unique(t+1,t+n+1)-t-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(t+1,t+m+1,a[i])-t;//用lower_bound O(log n)查找比for O(n)更快
memset(e,0,sizeof(e));
for(i=1;i<=n;i++){
addto(a[i],1); //这里与模板2不同,需要先把初值加入树状数组
res=res+i-query(a[i]);
}
return res;
}