树状数组第一题，上来就是二维树状数组，这是逼着我用树状数组做啊，二维线段树不会写啊~~
题目大意：
给定矩阵大小，可以更新矩阵中的某些数，要求输出某个范围内的所有数之和。
解题思路：
二维树状数组可解。
一维树状数组讲解：点击打开。
二维树状数组只是在更新方式上稍作改变。
在数组长度为n的树状数组中：
寻找下一个需要添加的数的下标：
int lowbit(int x) { return x&(-x); }
一维树状数组更新是这样的：
void add(int x,int val) { for(;x<=n;x+=lowbit(x)) { num[x]+=val; } } 二维树状数组更新是这样的： void add(int x,int y,int val) { for(int i=x;i<=s;i+=lowbit(i)) { for(int j=y;j<=s;j+=lowbit(j)) { num[i][j]+=val; } } }
一维树状数组查询是这样的：
int query(int x) { int ans=0; for(;x>0;x-=lowbit(x)) { ans+=c[i]; } return ans; }
查询的是1到x的数总和。
二维树状数组查询是这样的int query(int x,int y) { int ans=0; for(int i=x;i>0;i-=lowbit(i)) { for(int j=y;j>0;j-=lowbit(j)) { ans+=num[i][j]; } } return ans; } 查询的是（1，1）到（x，y）的数的总和。
下面是代码：
#include <stdio.h> #include <string.h> int num[1050][1050],s; int lowbit(int x) { return x&(-x); } void add(int x,int y,int val) { for(int i=x;i<=s;i+=lowbit(i)) { for(int j=y;j<=s;j+=lowbit(j)) { num[i][j]+=val; } } } int query(int x,int y) { int ans=0; for(int i=x;i>0;i-=lowbit(i)) { for(int j=y;j>0;j-=lowbit(j)) { ans+=num[i][j]; } } return ans; } int main() { int t,q,x,y,sum,l,r,a; scanf("%d%d",&t,&s); memset(num,0,sizeof(num)); while(scanf("%d",&q),q<3) { if(q==1) { scanf("%d%d%d",&x,&y,&a); x++; y++; add(x,y,a); } else if(q==2) { scanf("%d%d%d%d",&x,&y,&l,&r); x++; y++; l++; r++; printf("%d\n",query(l,r)-query(l,y-1)-query(x-1,r)+query(x-1,y-1)); } } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996675.html
相关资源：JAVA上百实例源码以及开源项目