树状数组小结-二维

树状数组:
模板:
取数组下标二进制非0最低位所表示的值;
区间查询。
单点更新:

同一维树状数组比较,这样比较好理解;
如果一维不会可以看看我的一维树状数组博客
1.一维二维都是:取数组下标二进制非0最低位所表示的值;

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

2. 一维树状数组更新是这样的:

void add(int x,int val)
{
    for(;x<=n;x+=lowbit(x))
    {
        num[x]+=val;
    }
}

二维树状数组更新是这样的:

void  add(int x,int y,int val)
{
    for(int i=x;i<=s;i+=lowbit(i))
    {
        for(int j=y;j<=s;j+=lowbit(j))
        {
            num[i][j]+=val;
        }
    }
}

3.一维树状数组查询是这样的:

int query(int x)
{
    int ans=0;
    for(;x>0;x-=lowbit(x))
    {
        ans+=c[i];
    }
    return ans;
}

二维树状数组查询是这样的:

int query(int x,int y)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
    {
        for(int j=y;j>0;j-=lowbit(j))
        {
            ans+=num[i][j];
        }
    }
    return ans;
}

说说对二维的理解,其实就是数组的改变,变成二维呈次的形式,那么代码上是很好理解的,但和一维树状数组一样解释,就有点多余。自行理解;

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int su[1050][1050],s;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y,int v)
{
    for (int i=x; i<=s; i+=lowbit(i))
        for (int j=y; j<=s; j+=lowbit(j))
            su[i][j]+=v;
}
int sum(int x,int y)
{
    int ans=0;
    for (int i=x; i>0; i-=lowbit(i))
        for (int j=y; j>0; j-=lowbit(j))
            ans+=su[i][j];
    return ans;
}
int n,m,p,x1,x2,y1,y2,tmp;
int main()
{
    while(scanf("%d",&p))
    {
        if (p==0) scanf("%d",&s);
        if (p==3) return 0;
        if (p==1)
        {
            scanf("%d%d%d",&x1,&y1,&tmp);
            x1++;
            y1++;
            add(x1,y1,tmp);
        }
        else if (p==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;
            y1++;
            x2++;
            y2++;
            int yy=sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1);
            printf("%d\n",yy);
        }
    }
    return 0;
}

全部评论

相关推荐

11-14 16:13
已编辑
重庆科技大学 测试工程师
Amazarashi66:不进帖子我都知道🐮❤️网什么含金量
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务