1.分块思想：

2.树状数组

//该函数是返回前x个整数之和 int getSum(int x) { int sum=0; for(int i=x; i>0; i-=lowbit(i)) { sum+=c[i]; } return sum; }

void update(int x, int v) { for(int i=x; i<=n; i+=lowbit(i)) c[i]+=v; }

数状数组最经典的应用

#include<iostream> using namespace std; const int maxn=10; #define lowbit(i) ((i)&(-i)) int n; int c[maxn]={0}; void update(int x, int v) { for(int i=x; i<maxn; i+=lowbit(i)) { c[i]+=v; } } int getNum(int x) { int sum=0; for(int i=x; i>0; i-=lowbit(i)) { sum+=c[i]; } return sum; } int main() { cin >> n; int temp; for(int i=0; i<n; i++) { cin >> temp; update(temp,1); cout << getNum(temp-1) << endl; //getNum(temp)就是统计temp左边小于等于temp的值的个数，而使用temp-1就是纯粹的去寻找比temp小的值的个数 } }

采用离散化的方式统计序列中在元素左边比该元素小的数字

#include<iostream> #include<cstring> using namespace std; //本题虽然是找在A[i]之前所有比A[i]小的数字的个数之和，注意我们随意输入数字，也不经过排序，但是c数组是统计x出现的个数 const int maxn=20; #define lowbit(i) ((i)&(-i)) //定义一个宏 int c[maxn]; void update(int x,int v) //对x位置的数增加v 统计数字x出现的次数 { for(int i=x; i<maxn; i+=lowbit(i)) //注意i每次增大lowbit(i) { c[i]+=v; //比如输入5它就在5这个位置将数字增加1 比如输入3它就在3这个位置数字增加1 } } int getNum(int x) //统计从位置x开始一直到前面所有的数字之和 { int sum=0; for(int i=x; i>0; i-=lowbit(i)) //注意i每次递减lowbit { sum+=c[x]; } return sum; } int main() { int n; cin >> n; int temp; memset(c,0,sizeof(c)); for(int i=0; i<n; i++) { cin >> temp; update(temp,1); cout << getNum(temp-1) << endl; } }