目录

树状数组的作用

（1）树状数组的经典模板

（2）关于记忆模板

楼兰图腾

我不会数学证明，但我可以学，会用就行，你知道我听了y总讲了一个小时证明的痛楚吗

树状数组的作用

1. 单点增加（时间复杂度为O (logN) ）
2. 区间查询前缀和（时间复杂度为O (logN) ）
3. 求逆序对（但是不如归并排序）
4. 扩展：差分+公式

相较于原数组a[N]，单点增加的时间复杂度为O(1)，但区间查询和的时间复杂度为O(N)

相较于前缀和数组pre[N]，区间查询和的时间复杂度为O(1)，但单点增加的复杂度为O(N)

因此我们选择了折中的办法就是 让这两个操作都为logN的复杂度 

（1）树状数组的经典模板

#include
#include
using namespace std;

const int N=1e5+10;
int a[N];
int tr[N];
int n;//点数

int lowbit(int x)
{
    return x & -x;
}

void add(int x,int c)//在x的位置上加上常数c
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)//求x位置前的前缀和
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(1)
    {
        cout<<"第一次查询前缀和(1)"< 
（2）关于记忆模板 
 
 首先先把这张图记住
对于add函数，因为树状数组维护的是一部分树的前缀和，那么因此，它只能影响到这个位置及其后面的树状数组，因为需要将后面的树状数组更新，那么以lowbit(i)为单位向后更新
对于sum函数，因为树状数组维护的是一部分树的前缀和，因此它向前查询，其中每一段的大小是lowbit(i)，用res变量记录每一段树状数组的累计和，返回即可
如果还不理解的话，多写几遍，或者回去看证明= - =
 

楼兰图腾 
241. 楼兰图腾 - AcWing题库
 
核心思路：
 
（乘法原理）我们可以知道，枚举中间的一个点，统计其左右两边满足条件的数量，那么左右两边的乘积结果就是 一个结果；举个例子：比如我们要求’V‘型的 点的个数，那么可以先预处理出 在第i个位置 ，其左边的点高于中间点的高度的个数，和右边的点高于中间点的高度的个数，然后相乘就是 枚举到的该点作为中间点的个数
 那么现在的问题就是<在一个区间中 快速地求出 小于或大于这个点的高度的 个数>
注意此时因为目标是 数字的个数，而非数字的大小，这启发了我们对于一个位置上的值，它是 数字的个数更为合理；那么对于这个位置而言呢，注意 条件是 <小于或大于这个数>，也就是说数的大小其实是作为 键的，也就是索引
问题分析到这里已经有了些许眉目，接下来的细节请看代码+详细注释
#include
#include
#include
using namespace std;

const int N=2000010;
typedef long long ll;
int n;
int a[N],t[N];//t[i]表示树状数组i结点覆盖的范围和
//Lower[i]表示左边比第i个位置小的数的个数
//Greater[i]表示左边比第i个位置大的数的个数
int Lower[N],Greater[N];

//返回非负整数x在二进制表示下最低位1及其后面的0构成的数值
int lowbit(int x)
{
    return x&-x;
}

//将序列中第x个数加上k
void add(int x,int k)//向右上方以lowbit(i) 为单位 在t数组中 区间加上k 维护
{
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=k;
}

//查询序列前x个数的和
int ask(int x)//向左上方以lowbit(i) 为单位 查询
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=t[i];
    return sum;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    从左向右，依次统计每个位置左边比第i个数y小的数的个数、以及大的数的个数
    for(int i=1;i<=n;i++)
    {
        int y=a[i];//第i个数

        //在前面已加入树状数组的所有数种统计在区间[1,y-1]的数字 的出现次数
        Lower[i]=ask(y-1);
        
        //在前面已加入树状数组的所有数中统计在区间[y+1,n]的数字 的出现次数
        Greater[i]=ask(n)-ask(y);
        
        将y加入树状数组，即数字y出现1次
        add(y,1);//注意这里的y是a[i]，也就是数字的大小，因为是已经按位置进行枚举的了
        //因此，不需要考虑 位置的先后顺序，而只用考虑数字的大小关系
    }

    //清空树状数组，从右往左统计每个位置右边比第i个数y小的数的个数、以及大的数的个数
    memset(t,0,sizeof t);

    ll resA=0,resV=0;
    //从右往左统计
    for(int i=n;i>=1;i--)
    {
        int y=a[i];

        resA+=(ll)Lower[i]*ask(y-1);//向右查询 [1,y-1]的数字的 总个数
        resV+=(ll)Greater[i]*(ask(n)-ask(y));//向右查询 [y+1,n]的数字的 总个数

        add(y,1);//同理
    }

    printf("%lld %lldn",resV,resA);

    return 0;
}
 

 
我累了，想不动了，看番了，明天再更