学步园

Problem Address：http://poj.org/problem?id=1195

【前言】

开始接触树状数组。

其实之前有看过一下相关内容，大体也是了解的，只是还没有用代码实现。

本来想找一道纯一维的来做，找了许久都找不到，干脆选了一道纯二维的。发现其实差别不是很大。

这道题也是稍微的磕磕碰碰地写了下来。

【一维】

百度树状数组：http://baike.baidu.com/view/1420784.htm#sub1420784

自己找找资料看一下内容。

主要有一个函数和两个操作：

（1）lowbit()函数：用于求出这个节点管辖的区间。

（2）修改操作：修改本节点，递归修改管辖这个节点的节点。

（3）求和操作：计算本节点管辖的和以及非管辖范围的和，递归求出非管辖范围的和。

其实几个函数写起来都是很简单的，从二维的代码中是可以看出一维的代码是如何完成的。

【二维】

关键是修改和求和操作。

对应于一维，X轴会有一个树状数组，Y轴会有一个树状数组，把X轴和Y轴相乘，就可以得到一个二维的树状数组。

所以，修改和求和的时候和一维是相似的，不同的地方在于把一重循环改成二重循环。

还有一个要注意的点，就是求和时使用容斥原理。

一维数组求某个区间的和时，如x到y，则S[x...y] = S[0...y] - S[0...x-1]，

而二维数组求某个区间的和时，如(l,b)到(r,t)，则S[(l,b)...(r,t)] = S[(0,0)...(r,t)] - S[(0,0)...(r,b-1)] - S[(0,0)...(l-1,t)] + S[(0,0)...(l-1,b-1)]。

【代码】

#include <iostream><br /> using namespace std;<br /> int map[1500][1500];<br /> inline int lowbit(int x)<br /> {<br /> return (x&(-x));<br /> }<br /> void update(int n, int x, int y, int a)<br /> {<br /> int i,j;<br /> for (i=x; i<=n; i+=lowbit(i))<br /> {<br /> for (j=y; j<=n; j+=lowbit(j))<br /> {<br /> map[i][j] += a;<br /> }<br /> }<br /> }<br /> int sum(int x, int y)<br /> {<br /> int i,j,s=0;<br /> for (i=x; i>0; i-=lowbit(i))<br /> {<br /> for (j=y; j>0; j-=lowbit(j))<br /> {<br /> s += map[i][j];<br /> }<br /> }<br /> return s;<br /> }<br /> int getsum(int l, int b, int r, int t)<br /> {<br /> return (sum(r,t)-sum(r,b-1)-sum(l-1,t)+sum(l-1,b-1));<br /> }<br /> int main()<br /> {<br /> int s,x,y,l,b,r,t,a;<br /> int i,j;<br /> int instr;<br /> scanf("%d %d", &instr, &s);<br /> for (i=1; i<=s; i++)<br /> {<br /> for (j=1; j<=s; j++)<br /> map[i][j] = 0;<br /> }<br /> while(scanf("%d", &instr)!=EOF)<br /> {<br /> if (instr==3) break;<br /> if (instr==1)<br /> {<br /> scanf("%d %d %d", &x, &y, &a);<br /> update(s, x+1, y+1, a);<br /> }<br /> else if (instr==2)<br /> {<br /> scanf("%d %d %d %d", &l, &b, &r, &t);<br /> printf("%d/n", getsum(l+1,b+1,r+1,t+1));<br /> }<br /> }<br /> return 0;<br /> }

【P.S】

接下来继续努力学习！