The article directories

• Tree array
• sample
• • The question
  • Analysis of the
  • code
• summary

Tree array

• What is a tree array? In simple terms, it is a violent traversal of a number to solve the interval problem, etc., but the traversal of the path is compressed with bit operation, complexity O(log2(n)) so that it does not time out. .
• Lowbit () operation
  
  At its core is the magical Lowbit operation, lowbit(x)=x&(-x)The last 1 in the binary number of x, the principle is represented by the complement of negative numbers, which is the inverse plus one of the original code. For example, x = 6 = 00000110 (2), – x = x = 11111010 (2), then lowbit (x) = x & (x) = 10 (2) = 2.
  
  Lowbit () : a[x] : a[x] : a[x] : a[x] : a[x]
  
  
  
  Graphical:
  
  
  
  Then through a [] arrays, and can sum, such as sum (8) = [8], a sum (7) = a + a + [6] [7] a [4], the sum (6) = a [6] + [4], so not is the path of the compression?
  
  Similarly, to update ax, update a[]; for example, to update A3, change a[3] first; Then 3+lowbit(3)=4, change a[4]; Then 4+lowbit(4)=8, change a[8].
• Two dimensional tree array
  
  Accordingly, we can derive a two-dimensional tree array, such as the interval input coordinates (x,y) obtained by updating points, and the yellow region of sum obtained by (u,v), as shown in the figure below:
  
  
  
  By figure comes easily to the yellow area for interval to sum (u, v) – the sum (x – 1, v) – the sum (u, y – 1) + sum (1 x, y)

sample

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
Copy the code

1
0
0
1
Copy the code

The question

Invert one submatrix at a time in an n by n matrix (0 becomes 1,1 becomes 0) and ask several times whether a point is 0 or 1.

Analysis of the

code

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 1003;
char s[5];
int a[maxn][maxn], n;
int lowbit(int x) {
	return (x & (-x));
}
void update(int x, int y) {
	for (int i = x; i <= n; i += lowbit(i)) {
		for (int j = y; j <= n; j += lowbit(j)) { a[i][j]++; }}}int sum(int x, int y) {
	int res = 0;
	for (int i = x; i > 0; i -= lowbit(i)) {
		for (int j = y; j > 0; j -= lowbit(j))
			res += a[i][j];
	}
	return res;
}
int main(a) {
	int ca, t;
	int x, y, u, v;
	scanf("%d", &ca);
	while (ca--) {
		memset(a, 0.sizeof(a));
		scanf("%d%d", &n, &t);
		while (t--) {
			scanf("%s%d%d", s, &x, &y);
			if (s[0] = ='C') {
				scanf("%d%d", &u, &v);
				x++, y++;
				u++, v++;
				update(u, v);
				update(x - 1, y - 1);
				update(x - 1, v);
				update(u, y - 1);
			}
			else {
				printf("%d\n".sum(x, y) % 2); }}printf("\n");
	}
	return 0;
}
Copy the code

summary