POJ 2155 매트릭스 (2 차원 트 리 배열 + 배열 배열 구간 업데이트 + 단일 조회)

Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N). 
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions. 
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2). 
2. Q x y (1 <= x, y <= n) querys A[x, y]. 
Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case. 
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above. 
Output
For each querying output one line, which has an integer representing A[x, y]. 
There is a blank line between every two continuous test cases. 
Sample Input

1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

Sample Output

1
0
0
1

문제 풀이:
제목 은 n * n 크기 의 2 차원 행렬 을 주 는 것 이다. 처음에 모두 0 이 었 고 그 다음 에 조작 수 는 t 이다. 만약 에 출력 문자 가 'Q' 라면 행렬 x, y 위치의 값 을 묻 고 'C' 인 다음 에 두 개의 점 좌 표를 출력 하여 행렬 의 왼쪽 상단 과 오른쪽 하단 좌 표를 나타 내 고 이 행렬 안의 값 을 반대 하 는 것 이다.선분 트 리 로 어떻게 하 는 지 모 르 겠 지만 2 차원 트 리 배열 의 블 로 그 를 보고 알 아 봤 다.
먼저 이 문 제 를 쓰 고 트 리 배열 의 구간 을 업데이트 해 야 합 니 다. 맞아요. 트 리 배열 도 구간 을 업데이트 할 수 있 습 니 다. 원리 가 잘 모 르 겠 습 니 다. qaq 는 제 가 먼저 방법 을 말씀 드 리 겠 습 니 다. 만약 에 한 구간 x, y 에 값 v 를 추가 하려 면 배열 sum [x] 에 v 를 추가 하고 sum [y + 1] 에서 v 를 빼 면 구간 업데이트 가 완 성 됩 니 다. 다른 것 은 조회 점 에서 x 의 상황 을 조회 할 때 입 니 다.한 점 의 값 은 sum [1] +... + sum [x] 이 고 누적 하면 한 점 의 값 입 니 다.
어떻게 나의 이 해 를 말 합 니까?
sum [x] 에 v 를 추가 합 니 다. 업 데 이 트 는 나중에 업 데 이 트 됩 니 다 (매번 x & (- x) 를 추가 합 니 다). 그래서 이때 뒤의 구간 마다 v 를 추가 한 다음 에 sum [y + 1] 에서 v 를 빼 면 구간 외 에 더 한 v 를 제거 하 는 것 과 같 습 니 다. 이것 은 [x, y] 에 v 를 추가 하 는 것 입 니 다. 여기 구간 업데이트 가 비교적 특수 하기 때 문 입 니 다.그래서 조회 할 때 매 점 의 값 은 앞의 구간 값 을 모두 더 해 야 합 니 다.내 가 말 해도 잘 모 르 는 것 같 아, 이렇게 하 자.
그리고 이 문 제 를 설명 하려 면 그림 을 그 려 야 하기 때문에 제 가 본 블 로 그 를 바로 붙 이 겠 습 니 다. 클릭 하여 링크 를 엽 니 다.
이 블 로그 의 그림 은 이 문제 에 대한 이해 에 도움 이 됩 니 다. 2 차원 에서 그림 이 n * n 이 라면 [x, y] 에 v 를 추가 하면 왼쪽 상단 좌표 [x, y] 에 해당 합 니 다. 오른쪽 하단 좌표 [n * n] 의 큰 사각형 에 모든 값 에 v 를 추가 한 다음 에 후속 작업 은 많이 자 른 곳 과 많이 자 른 곳 이 마지막 에 업 데 이 트 를 완 성 했 습 니 다.
코드:

#include
#include
#include