数星星 （C++ 树状数组）

1265. 数星星 - AcWing题库

分析：

星星是按纵坐标递增给我们的，如果纵坐标相同，就按横坐标来给

所以星星是从低到高，一行一行来给的

题目要求我们去求每个等级的星星各有多少个

星星的等级由它左下角（包括左边和下边）的星星个数来决定的

我们来抽象一下他的操作是什么：

1️⃣在某个位置上A[i]+1

2️⃣求A1 ~ Ax的前缀和

观察到一个边插入边求前缀和的数据结构，想到了树状数组

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 32010;

int n;
int tr[N],level[N];

//树状数组三个基本操作
int lowbit(int x) {
    return x & -x;
}

int add(int x) {
    for(int i = x;i <= N;i += lowbit(i)) tr[i] ++;
}

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

int main () {
    
    scanf("%d",&n);
    
    for (int i = 0;i < n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        x++; // 0≤x  树状数组下标一定要从1开始 所以所有星星向右移一个单位 
        //在添加星星之前先查询，否则需要在查询后减去自己 比较麻烦
        level[sum(x)]++;//表示该等级的星星增加一个
        add(x);
    }
    
    for (int i = 0;i < n;i++) {
        printf("%d\n",level[i]);
    }
    
    return 0;
    
}

如果在查询前先添加，则等级都会加1：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 32010;

int n;
int tr[N],level[N];

//树状数组三个基本操作
int lowbit(int x) {
    return x & -x;
}

int add(int x) {
    for(int i = x;i <= N;i += lowbit(i)) tr[i] ++;
}

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

int main () {
    
    scanf("%d",&n);
    
    for (int i = 0;i < n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        x++; 
        
        add(x);
        level[sum(x)]++;//表示该等级+1的星星增加一个
        
    }
    
    for (int i = 1;i < n+1;i++) {
        printf("%d\n",level[i]);
    }
    
    return 0;
    
}