二维树状数组-POJ 2155 Matrix

梦里梦外; 2023-05-22 14:25 17阅读 0赞

### 文章目录 ###

*  树状数组
 *  例题
 *   *  题意
     *  分析
     *  代码
 *  小结

# 树状数组 #

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

*  **什么是树状数组？**  
    简单来说，就是暴力遍历数组来解决区间问题等，**不过**遍历的路径使用了位运算来进行压缩，复杂度是O(log2(n))这样就不会超时了（为所欲为？）。
 *  **lowbit()操作**  
    其核心是神奇的lowbit操作，lowbit(x)=x&(-x)，它的功能是找到**x的二进制数的最后一个1**，原理是利用负数的补码表示，补码是原码取反加一。例如x=6=00000110(2)，-x=x补=11111010(2)，那么lowbit(x)=x&(-x)=10(2)=2。  
    从lowbit()引出数组a\[\]，a\[x\]的值是把ax(题目输入初始值)和他前面的m个数相加，如下表所示：  
    ![在这里插入图片描述][20200418115151537.png]  
    图形化：  
    ![在这里插入图片描述][20200418115210387.png]  
    那么通过数组a\[\]，就可以求sum,例如sum(8)=a\[8\]，sum(7)=a\[7\]+a\[6\]+a\[4\]，sum(6)=a\[6\]+a\[4\]，如此一来不就是我们要的路径压缩了吗？  
    同样地，更新ax时也要更新a\[\]，例如更新a3，那么首先更改a\[3\]；然后3+lowbit(3)=4,更改a\[4\]；接着4+lowbit(4)=8，更改a\[8\]。
 *  **二维树状数组**  
    相应的，我们可以推导出二维树状数组，例如更新点求区间输入坐标(x,y),(u,v)求sum黄色区域，如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70]  
    由图易得所求区间黄色区域为sum(u,v)-sum(x-1,v)-sum(u,y-1)+sum(x-1,y-1)

# 例题 #

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

[POJ-2155][]

> 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.

**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矩阵中每次对一个子矩阵进行翻转（0变1,1变0），然后多次询问某个点是0还是1。

## 分析 ##

更新区间求点，用二维树状数组解决，每次更新子矩阵+1，最后求点%2就得到结果。（其实就是二维数组模拟的思路，压缩路径罢了）。

## 代码 ##

#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() { 
    	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;
    }

# 小结 #

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

1.  树状数组能解决的题都能用线段树解决，但是树状数组编程复杂度低，完成效率更高！(大佬请无视)

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://blog.csdn.net/qq\_45034708][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[20200418115151537.png]: /images/20230521/67a107558ee0450a90d37692da212816.png
[20200418115210387.png]: /images/20230521/d760914d11614c479ccc94de2bf77c76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70]: /images/20230521/f29a104e01584f8482ca14ea67a83559.png
[POJ-2155]: http://poj.org/problem?id=2155
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708