2 条题解

  • 0
    @ 2025-10-8 16:58:40
    #include<bits/stdc++.h> 
    using namespace std;
    typedef long long LL;
    const int N=(1<<12)+10;
    int n,m;LL s[N][N];
    void add(int x,int y,int k)
    {
        for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=m;j+=j&-j)s[i][j]+=k;
    }
    LL getsum(int x,int y)
    {
        LL res=0;
        for(int i=x;i>=1;i-=i&-i)for(int j=y;j>=1;j-=j&-j)res+=s[i][j];
        return res;
    }
    int main()
    {
        scanf("%d%d", &n, &m);
        memset(s,0,sizeof(s));
        int op,k,x,y,a,b,c,d;
        while(scanf("%d", &op)!=EOF)
        {
            
            if(op==1)scanf("%d%d%d", &x, &y, &k), add(x,y,k);
            else
            {
                scanf("%d%d%d%d", &a, &b, &c, &d);
                printf("%lld\n", getsum(c,d)-getsum(c,b-1)-getsum(a-1,d)+getsum(a-1,b-1));
            }
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:58:30
      #include<bits/stdc++.h> 
      using namespace std;
      typedef long long LL;
      const int N=(1<<12)+10;
      int n,m;LL s[N][N];
      void add(int x,int y,int k)
      {
          for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=m;j+=j&-j)s[i][j]+=k;
      }
      LL getsum(int x,int y)
      {
          LL res=0;
          for(int i=x;i>=1;i-=i&-i)for(int j=y;j>=1;j-=j&-j)res+=s[i][j];
          return res;
      }
      int main()
      {
          scanf("%d%d",&n,&m);
          memset(s,0,sizeof(s));
          int op,k,x,y,a,b,c,d;
      	while(scanf("%d",&op)!=EOF)
          {
              
              if(op==1)scanf("%d%d%d",&x,&y,&k),add(x,y,k);
              else
      		{
      			scanf("%d%d%d%d",&a,&b,&c,&d);
      			printf("%lld\n",getsum(c,d)-getsum(c,b-1)-getsum(a-1,d)+getsum(a-1,b-1));
      		}
          }
          return 0;
      }
      • 1

      二维树状数组 1:单点修改,区间查询

      信息

      ID
      1805
      时间
      1000ms
      内存
      256MiB
      难度
      7
      标签
      (无)
      递交数
      144
      已通过
      32
      上传者