2 차원 나무 모양 배열 - SuperBrother 두더지 때 리 기 (Vijos 1512)

트 리 배열 (BIT) 은 로그 (n) 의 복잡 도 를 조회 하고 수정 하 는 데이터 구조 로 주로 두 자리 사이 의 모든 요 소 를 조회 하 는 데 사용 되 며 프로 그래 밍 이 간단 하고 쉽게 이 루어 집 니 다.2 차원 까지 쉽게 확장 할 수 있 습 니 다.누 드 2 차원 나무 모양 의 배열 문 제 를 살 펴 보 자.
    두 더 지 를 때 리 는 게임 에서 두 더 지 는 때때로 동굴 에서 뚫 고 나 오지 만 동굴 입구 로 뚫 고 들 어가 지 않 는 다.동굴 입 구 는 모두 n (n < = 1024) 크기 의 정사각형 에 있다.이 정사각형 은 평면 직각 좌표계 에서 왼쪽 아래 는 (0, 0) 이 고 오른쪽 상단 은 (n - 1, n - 1) 이다.동굴 입구 가 있 는 위 치 는 모두 정각 이 고 가로 세로 좌표 가 모두 정수 인 점 이다.슈퍼 브 라 더 는 어떤 범위 의 두더지 총 수 를 알 고 싶 어 한다.이것 이 바로 너의 임무 다.
입력 파일 마다 여러 줄 이 있 습 니 다.첫 번 째 줄 은 두더지 의 범 위 를 나타 낸다.이후 각 줄 의 시작 부분 에 하나의 수 m 가 있 는데 서로 다른 조작 을 나타 낸다. m = 1, 그러면 뒤에 3 개의 수 x, y, k (0 < = x, y < n) 를 따라 점 (x, y) 에서 k 마리 의 두더지 가 새로 나 타 났 음 을 나타 낸다.m = 2, 그러면 뒤에 4 개의 수 x1, y1, x2, y2 (0 < = x1 < = x2 < n, 0 < = y1 < = y2 < n) 를 따라 직사각형 (x1, y1) - (x2, y2) 내의 두더지 수량 을 묻는다.선생님 이 오 셔 서 못 놀 겠 다 는 뜻 이에 요.이 숫자 가 입력 의 마지막 줄 에 있 을 것 을 보증 합 니 다.
문의 수 는 10000 을 초과 하지 않 고 두더지 수 는 maxlongint 를 초과 하지 않 습 니 다.
이 문 제 를 간단하게 추상 화하 다.바로:

1 을 입력 할 때 2 차원 행렬 의 특정한 위치 에 k 를 추가 합 니 다.

2 를 입력 할 때 행렬 의 [(x1, y1), (x2, y2)] 의 하위 행렬 에서 요소 의 총 크기 를 구하 고 출력 합 니 다.

3 을 입력 하면 종료 합 니 다.

이 문 제 는 입력 데이터 규모 가 클 수 있 습 니 다.그리고 동적 수정 으로 접두사 와 접 두 사 를 사용 할 수 없 기 때문에 트 리 배열 이 우리 의 최 우선 선택 입 니 다.그러나 나무 모양 의 배열 은 원래 1 차원 인 데 어떻게 2 차원 으로 보급 할 수 있 습 니까?사실은 매우 간단 하 다. 그 방법 은 선생님 이 원 배열 의 1 차원 나무 모양 배열 과 유사 하 다. 그리고 1 차원 나무 모양 배열 을 2 차원 으로 조합 하 는 대응 관 계 는 다음 과 같다.
　　C[1][1]=a[1][1],C[1][2]=a[1][1]+a[1][2],C[1][3]=a[1][3],C[1][4]=a[1][1]+a[1][2]+a[1][3]+a[1][4],c[1][5]=a[1][5],C[1][6]=a[1][5]+a[1][6],... 
　　C[2][1]=a[1][1]+a[2][1],C[2][2]=a[1][1]+a[1][2]+a[2][1]+a[2][2],C[2][3]=a[1][3]+a[2][3],C[2][4]=a[1][1]+a[1][2]+a[1][3]+a[1][4]+a[2][1]+a[2][2]+a[2][3]+a[2][4], C[2][5]=a[1][5]+a[2][5],C[2][6]=a[1][5]+a[1][6]+a[2][5]+a[2][6],...
　　C[3][1]=a[3][1],C[3][2]=a[3][1]+a[3][2],C[3][3]=a[3][3],C[3][4]=a[3][1]+a[3][2]+a[3][3]+a[3][4],C[3][5]=a[3][5],C[3][6]=a[3][5]+a[3][6],... 
C [4] [1] = a [1] [1] + a [2] [1] + a [3] [1] + a [4] [1] = a [1] [1] + a [2] [1] + a [2] [2] + a [3] [1] + a [3] [2] + a [4] [1] + a [4] [4] [2], C [4] [3] = a [3] [3] + a [3] + a [4],... (너무 많 으 면 3 까지 쓰 겠 습 니 다) 
　　……
관찰 을 통 해 알 수 있 듯 이 첫 번 째 줄 은 그 자체 이 고 두 번 째 줄 은 그 자체 이 며 세 번 째 줄 은 그 자체 이 고 네 번 째 줄 은 첫 번 째, 두 번 째 줄 에 그 자 체 를 더 한 것 이다.이것 은 1 차원 의 나무 모양 배열 과 같다.그래서 우 리 는 쉽게 수정, 조회 함 수 를 쓸 수 있다.

void modfily(int x,int y,int data){

    x+=1;y+=1;

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

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

            c[i][j]+=data;

}

int sum(int x,int y){

    x+=1;y+=1;

    int result=0;

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

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

            result+=c[i][j];

    return result;

}

이것 이 바로 2 차원 트 리 배열 의 핵심 입 니 다. 코드 는 1 차원 과 비슷 하고 매우 간단 합 니 다.왜 i, j 가 1 을 넣 어야 하 는 지 의문 이 있 을 수 있 습 니 다.사실 이것 은 제 가 구덩이 에 빠 진 후에 깨 달 은 것 입 니 다. 만약 에 i, j = 0 이 라면 lowbit 도 영원히 0 이 고 프로그램 은 순환 에 빠 질 것 입 니 다. 직접 TLE 입 니 다.이 두 함수 에서 우 리 는 2 차원 트 리 배열 의 조회, 수정 시간 복잡 도 는 log (n) 임 을 알 수 있다.²。
데이터 구조 부분 이 해결 되 었 는데 어떻게 하위 행렬 의 수의 합 을 구 합 니까?그림 을 그리 면 우 리 는 구 할 수 있다. 공식 은 sum (x2, y2) - sum (x1 - 1, y2) - sum (x2, y1 - 1) + sum (x1 - 1, y1 - 1) 이다.
참고 로 이 예제 의 AC code 를 동봉 합 니 다.

#include <cstdio>

#include <cstdlib>

using namespace std;



int m=0,n,x,y,k,x1,y1,c[1026][1026];

void modfily(int,int,int);

int sum(int,int);

inline int lowbit(int x){

    return x&(-x);

}



int main(void){

    scanf("%d",&n);

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

        for (int j=0;j<n;++j)   c[i][j]=0;

    while (m!=3){

        scanf("%d",&m);

        if (m==1){

            scanf("%d%d%d",&x,&y,&k);

            modfily(x,y,k);

        }

        if (m==2){

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

            printf("%d
",abs(sum(x1,y1)-sum(x-1,y1)-sum(x1,y-1)+sum(x-1,y-1)));

        }

    }

    return 0;

}

void modfily(int x,int y,int data){

    x+=1;y+=1;

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

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

            c[i][j]+=data;

}

int sum(int x,int y){

    x+=1;y+=1;

    int result=0;

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

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

            result+=c[i][j];

    return result;

}