跳到主要内容

树状数组

树状数组完成以下两种操作：

  1. 将第i个数加上k
  2. 输出区间[i,j]内每个数的和

lowbit(x)：返回x在二进制表示下最低位1

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

树状数组结构：

image.png

使用树形结构维护前缀和，时间复杂度为O(logn)

  1. 每个结点t[x]保存以x为根的子树中叶结点值的和
  2. 每个结点覆盖的长度为lowbit(x)
  3. t[x]结点的父结点为t[x + lowbit(x)]
  4. 树的深度为log2n+1

加数操作：

void add(int x, int k)
{
    for(int i = x; i <= n; i += lowbit(i))
        t[i] += k;
}

在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确

查询操作

int ask(int x)
{
    int sum = 0;
    for(int i = x; i; i -= lowbit(i))
        sum += t[i];
    return sum;
}

查询这个点的前缀和，需要从这个点向左上找到上一个结点，将加上其结点的值。向左上找到上一个结点，只需要将下标 x -= lowbit(x)

AcWing 241. 楼兰图腾​

题目​

https://www.acwing.com/problem/content/243/ 在完成了分配任务之后，西部 314 来到了楼兰古城的西部。 相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(V)，一个部落崇拜铁锹(∧)，他们分别用 V 和 ∧ 的形状来代表各自部落的图腾。 西部 314 在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了 n 个点，经测量发现这 n 个点的水平位置和竖直位置是两两不同的。 西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关，因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)，其中y1∼yn是 1 到 n 的一个排列。 西部 314 打算研究这幅壁画中包含着多少个图腾。 如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi>yj,yj<yk，则称这三个点构成 V 图腾; 如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi<yj,yj>yk，则称这三个点构成 ∧ 图腾; 西部 314 想知道，这 n 个点中两个部落图腾的数目。 因此，你需要编写一个程序来求出 V 的个数和 ∧ 的个数。

思路​

  1. 遍历数组中每个数a[i],使用树状数组统计在位置之前所有比a[i]大的数，以及所有比a[i]小的数的个数
  2. 倒叙遍历每个数a[i],使用树状数组统计在i之后所有比a[i]大的数，以及小的数的个数
  3. 统计完后，将a[i]加入到树状数组中

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N=200010;

int n;
int a[N];
int tr[N];//tr[i]表示树状数组i结点覆盖的范围和
int Greater[N],lower[N];//Lower[i]表示左边比第i个位置小的数的个数
int lowbit(int x){return x&-x;}

//将序列中第x个数加上k。
void add(int x,int c){
    for(int i=x;i<=n;i+= lowbit(i)){
        tr[i]+=c;
    }
}
//查询序列前x个数的和
int sum(int 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];

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        Greater[i]= sum(n)- sum(y);
        lower[i]= sum(y-1);
        add(y,1);//将y加入树状数组，即数字y出现1次
    }
    memset(tr,0,sizeof tr);
    LL res1=0,res2=0;
    for(int i=n;i;i--){
        int y=a[i];
        res1+=Greater[i]*(LL)(sum(n)- sum(y));
        res2+=lower[i]*(LL)(sum(y-1));
        add(y,1);
    }
    cout<<res1<<" "<<res2<<endl;
    return 0;
}

AcWing 242. 一个简单的整数问题​

题目​

https://www.acwing.com/problem/content/248/ 给定长度为 N 的数列 A，然后输入 M 行操作指令。 第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。 第二类指令形如 Q x，表示询问数列中第 x 个数的值。 对于每个询问，输出一个整数表示答案。

思路​

树状数组，区间修改，单点查询

差分操作

  1. b[l]+=d;
  2. b[r+1]-=d;

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N=100010;
int n,m;
int a[N];
LL tr[N];

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

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

LL sum(int x){
    LL res=0;
    for(int i=x;i;i-= lowbit(i)) res+=tr[i];
    return res;
}

int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) add(i,a[i]-a[i-1]);

    while (m--){
        char op[2];
        int l,r,d;
        cin>>op>>l;
        if (op[0]=='C'){
            cin>>r>>d;
            add(l,d), add(r+1,-d);
        }else {
            cout<<sum(l)<<endl;
        }
    }
    return 0;
}

0%