hiho 172周 - 二维树状数组模板题

题目链接

描述

You are given an N × N matrix. At the beginning every element is 0. Write a program supporting 2 operations:

1. Add x y value: Add value to the element A_xy. (Subscripts starts from 0

2. Sum x₁ y₁ x₂ y₁: Return the sum of every element A_xy for x₁ ≤ x ≤ x₂, y₁ ≤ y ≤ y₂.

输入

The first line contains 2 integers N and M, the size of the matrix and the number of operations.

Each of the following M line contains an operation.

1 ≤ N ≤ 1000, 1 ≤ M ≤ 100000

For each Add operation: 0 ≤ x < N, 0 ≤ y < N, -1000000 ≤ value ≤ 1000000

For each Sum operation: 0 ≤ x₁ ≤ x₂ < N, 0 ≤ y₁ ≤ y₂ < N

输出

For each Sum operation output a non-negative number denoting the sum modulo 10⁹+7.

----------------------------------------------------------------------------------------------------------------------

破题，non-negative number denoting the sum modulo ，wa了好几次

#include <cstdio>

#include <cstring>

#include <iostream>

typedef long long LL;

using namespace std;

const int N = ;

const LL MOD = 1e9+;

int n,m;

LL sum[N][N];

int lowbit(int data){

    return data&(-data);

}

void add(int x,int y,int d){

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

    for(int j=y;j<=n;j+=lowbit(j)){

        sum[i][j] += d;

        sum[i][j] %= MOD;

    }

}

LL query(int x,int y){

    LL ret = ;

    for(int i=x;i>;i-=lowbit(i))

    for(int j=y;j>;j-=lowbit(j)){

        ret += sum[i][j];

        ret %= MOD;

    }

    return ret;

}

int main(){

    cin>>n>>m; char str[];

    memset(sum,,sizeof(sum));

    int x1,y1,x2,y2,d;

    while(m--){

        scanf("%s",str);

        if(str[]=='A'){

            scanf("%d%d%d",&x1,&y1,&d);

            add(x1+,y1+,d);

        }

        else{

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            LL total = query(x2+,y2+);

            LL small = query(x1+,y1+);

            LL s1 = query(x2+,y1+);

            LL s2 = query(x1+,y2+);

            printf("%lld\n",((total+small-s1-s2)%MOD+MOD)%MOD);

        }

    }

    return ;

}

巴特西

hiho 172周 - 二维树状数组模板题

描述

输入

输出

最新文章

热门文章