SCAU-1144 数星星-HDU-1166-树状数组的应用

本文借鉴
代码提供：https://www.cnblogs.com/geek1116/p/5566709.html
树状数组详解：https://www.cnblogs.com/xenny/p/9739600.html
不知道树状数组的同学呢就看看上面的链接啦讲的很棒呢（在学习树状数组的时候其实是可以同时学一下线段树的）
在学习的时候可以看下这个题目，是可以用线段树来做也可以用树状数组来做的https://www.cnblogs.com/M-cag/archive/2012/08/16/2642459.html
核心呢还是这个：2^k = i&(-i)

C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]

如果是要修改了一个A[]的话会引起其他的c改变的，就要看那些的c[]包含了A[]
A[i] 包含于 C[i + 2k]、C[(i + 2k) + 2k]...；
还是打一下基本的代码把（我也练下）
下面用a[]来装原来的数组，然后用c[]来装树状数组的
算2^k的函数是lowbit

int lowbit(int x)//这里的x就是那个k了
{
return x&(-x);
}

如果是修改了A[]的话
void update(int i,int k)//在i位置上加k也就是改变了A[]
{
while(i<=n)//只要还在范围内的话就可以一直的修改了
{
c[i]+=k;
i+=lowbit(i);
}
}

求和的话
int getsum(int i)//求1到i的和
{
int res=0;
while(i>0)
{
res+=c[i];
i-=lowbit(i);
}
return res;
}

1144 数星星
该题有题解

时间限制:564MS 内存限制:65536K
提交次数:193 通过次数:43

题型: 编程题语言: G++;GCC

Description
天文学家们喜欢观察星星。它们把每颗星星看成一个点，并把每颗星星左下方（即横坐标和纵坐标都不比它大）的星星颗数作为它的等级值。
现给出所有星星（星星个数为N）的坐标，计算并输出指定编号的星星的等级。

注意：不存在相同坐标的星星

输入格式
第一行为N
后N行为编号为1到N的星星的坐标（坐标用整数）
此后是M
后一行是M个星星的编号

N<=100000
M<=1000

坐标范围0<=x,y<=1000000

输出格式
要求依次输出这M个星星的等级，一行一个

输入样例
5
0 0
2 0
3 0
1 1
2 2
2
4 5

输出样例
1
3

思路：一般这种输入x y坐标型的，或者一个物体是有两个属性的话，如果要进行比较的话，一帮都是先对其中一个变量进行排序，然后再吧问题变成了对另外一个变量的比较上了
由于如果要对结构体进行比较的话最好还是用到c++来搞，所以下面代码是用c++来实现的了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <queue>

#include <stack>

#include <map>

#include <vector>

#include <set>

#include <utility>

#define ll long long

#define inf 0x3f3f3f3f

#define MAX_N 100000

#define MAX_X 1000000

using namespace std;

typedef struct node

{

    int x,y;

    int p; //因为我们对数组进行了重新的排序，但是最好输入的是下标来看他的等级是多少的，所以为了之后可以输入下标得出结果，

     //就要再定义一个p来存放原来的下标值的

    //所以用个变量p来标记该元素的原下标

} node;

node star[MAX_N+];//

bool cmp(node a,node b) //按y大小升序来排序,y相同时把x较小的排前面

{

    if(a.y!=b.y)

        return a.y<b.y;

    else

        return a.x<b.x;

}

int n,m,maxn;//n表示的是有多少个星星，然后m是要看多少个星星的等级，用maxn来存放星星里面横坐标最大的那个

int ans[MAX_N+]; //ans[]数组存储每个星星的等级，这个数组的下标表示的是输入数的下标，而并不是x或者y

int bit[MAX_X+]; //树状数组中的统计和的数组，也就是那个c数组了

int sum(int pos)//就是板子了呢

{

    int res=;

    while(pos)

    {

        res+=bit[pos];//再次说bit[]就是板子里面的c[]

        pos-=(pos&-pos);

    }

    return res;

}

void updata(int pos,int value)//由于是以颗数来搞的，所以value其实就是1了，就是在相应的位置上加1的了

{

    while(pos<=maxn)

    {

        bit[pos]+=value;//把只要和pos位置有关的数组都加1，其实就是输入了这个位置说明就有这个点了，所以和这个点有光的所以的bit[]就加1即可了

        pos+=(pos&-pos);

    }

}

int main()

{

    //freopen("input.txt","r",stdin);

    memset(bit,,sizeof(bit));//这里是没有用到另外一个数组a[]来装原数组的

    scanf("%d",&n);

    maxn=-;

    for(int i=; i<=n; i++)

    {

        scanf("%d%d",&star[i].x,&star[i].y);

        star[i].x++;    //注意了：在树状下标不能有0,否则会死循环!

        star[i].y++;   //所以所有的横纵坐标都+1

        star[i].p=i;//就是下标，我们是从1开始到n的作为下标的

        if(star[i].x>maxn)

            maxn=star[i].x;  //更新最大的x坐标

    }

    sort(star+,star+n+,cmp);//以y坐标升序来sort

    //

    for(int i=; i<=n; i++)

    {

        ans[star[i].p]=sum(star[i].x); //计算位于其左下方的星星个数，注意这个ans是以这个点的输入的次序也就是下标来的

        updata(star[i].x,);  //更新bit[]数组

    }

    //

    scanf("%d",&m);

    while(m--)

    {

        int temp;

        scanf("%d",&temp);

        printf("%d\n",ans[temp]);

    }

    return ;

}

例题：

敌兵布阵

HDU - 1166

 #include <bits/stdc++.h>

 using namespace std;

 int n,m;

 int a[],c[]; //对应原数组和树状数组

 int lowbit(int x){

     return x&(-x);

 }

 void updata(int i,int k){    //在i位置加上k

     while(i <= n){

         c[i] += k;

         i += lowbit(i);

     }

 }

 int getsum(int i){        //求A[1 - i]的和

     int res = ;

     while(i > ){

         res += c[i];

         i -= lowbit(i);

     }

     return res;

 }

 int main(){

     int t;

     cin>>t;

     for(int tot = ; tot <= t; tot++){

         cout << "Case " << tot << ":" << endl;

         memset(a, , sizeof a);

         memset(c, , sizeof c);

         cin>>n;

         for(int i = ; i <= n; i++){

             cin>>a[i];

             updata(i,a[i]);   //输入初值的时候，也相当于更新了值,所有就直接的调用update函数即可了

         }

         string s;//存放的是指令

         int x,y;

         while(cin>>s && s[] != 'E'){//如果是E的话就结束了

             cin>>x>>y;//由于只要不是结束的话都是要输入两个数的 x和y的

             if(s[] == 'Q'){    //求和操作

                 int sum = getsum(y) - getsum(x-);    //x-y区间和也就等于1-y区间和减去1-(x-1)区间和

                 cout << sum << endl;

             }

             else if(s[] == 'A'){

                 updata(x,y);//在x的位置上加y

             }

             else if(s[] == 'S'){

                 updata(x,-y);    //减去操作，即为加上相反数

             }

         }

     }

     return ;

 }

其他的扩展：
区间更新、单点查询（差分建树）
核心：当某个区间[x,y]值改变了，区间内的差值是不变的，只有D[x]和D[也就是说问题变成了：原来要更新一个区间的值变成了只需要更新两个点y+1]的值发生改变，
所以我们就可以利用这个性质对D[]数组建立树状数组，
也就是说问题变成了只用在原来的基础上吧第x个的加k，然后第y+1个的减k即可了

 int n,m;

 int a[] = {},c[]; //对应原数组和树状数组

 int lowbit(int x){

     return x&(-x);

 }

 void updata(int i,int k){    //在i位置加上k

     while(i <= n){

         c[i] += k;

         i += lowbit(i);

     }

 }

 int getsum(int i){        //求D[1 - i]的和，即A[i]值

     int res = ;

     while(i > ){

         res += c[i];

         i -= lowbit(i);

     }

     return res;

 }

 int main(){

     cin>>n;     for(int i = ; i <= n; i++){

         cin>>a[i];

         updata(i,a[i] - a[i-]);   //输入初值的时候，也相当于更新了值

     }

     //[x,y]区间内加上k

     updata(x,k);    //A[x] - A[x-1]增加k

     updata(y+,-k);        //A[y+1] - A[y]减少k

     //查询i位置的值

     int sum = getsum(i);

     return ;

 }

区间更新、区间查询：还是利用了差分的思维了
核心：维护两个数状数组，sum1[i] = D[i]，sum2[i] = D[i]*(i-1);

 int n,m;

 int a[] = {};

 int sum1[];    //(D[1] + D[2] + ... + D[n])

 int sum2[];    //(1*D[1] + 2*D[2] + ... + n*D[n])

 int lowbit(int x){

     return x&(-x);

 }

 void updata(int i,int k){

     int x = i;    //因为x不变，所以得先保存i值

     while(i <= n){

         sum1[i] += k;

         sum2[i] += k * (x-);

         i += lowbit(i);

     }

 }

 int getsum(int i){        //求前缀和

     int res = , x = i;

     while(i > ){

         res += x * sum1[i] - sum2[i];

         i -= lowbit(i);

     }

     return res;

 }

 int main(){

     cin>>n;

     for(int i = ; i <= n; i++){

         cin>>a[i];

         updata(i,a[i] - a[i-]);   //输入初值的时候，也相当于更新了值

     }

     //[x,y]区间内加上k

     updata(x,k);    //A[x] - A[x-1]增加k

     updata(y+,-k);        //A[y+1] - A[y]减少k

     //求[x,y]区间和

     int sum = getsum(y) - getsum(x-);

     return ;

 }

区间修改、单点查询模板题目：https://www.luogu.org/problem/show?pid=3368

区间修改、区间查询模板题目：https://vjudge.net/problem/POJ-3468
最后再打波广告：https://www.cnblogs.com/xenny/p/9739600.html讲的实在是太好了

巴特西

SCAU-1144 数星星-HDU-1166-树状数组的应用

敌兵布阵

最新文章

热门文章