【树转数组】poj1195

本文主要是介绍【树转数组】poj1195，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
二维的树状数组：
更新某个元素时：
NO.1:c[n1],c[n2],c[n3],....,c[nm];
其中n1 = i,n(i+1) = ni+lowbit(ni);
nm+lowbit(nm)的值应该大于元素个数N。
NO.2:sum(k)=c[n1]+c[n2]+...+c[nm];
其中nm=k，n(i-1)=ni-lowbit(ni);
n1-lowbit(n1)的值应该小于0
----------------------------------------------------------------------
用二维的c[i][j]存储长条的和。。。、
---------------------------------------
元素的值加一个数：
void update(int x, int y, int a)
{for(int i=x; i<=s; i+=lowbit(i)){for(int j=y; j<=s; j+=lowbit(j))c[i][j] += a;}
}
---------------------------------------------------
int sum(int x, int y)矩阵0到x和0到y的元素和
{int ret = 0;for(int i=x; i>0; i-=lowbit(i)){for(int j=y; j>0; j-=lowbit(j))ret += c[i][j];}return ret;
}
------------------------------------------------
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3fusing namespace std;int op,s;
int x,y,a;
int l,b,r,t;
int c[1050][1050];int lowbit(int x)
{return x & (-x);
}void update(int x, int y, int a)
{for(int i=x; i<=s; i+=lowbit(i)){for(int j=y; j<=s; j+=lowbit(j))c[i][j] += a;}
}int sum(int x, int y)
{int ret = 0;for(int i=x; i>0; i-=lowbit(i)){for(int j=y; j>0; j-=lowbit(j))ret += c[i][j];}return ret;
}int main()
{//freopen("input.txt","r",stdin);while(1){scanf("%d",&op);if(op == 0){scanf("%d",&s);memset(c, 0, sizeof(c));}if(op == 1){scanf("%d%d%d",&x,&y,&a);update(x+1, y+1, a);}if(op == 2){scanf("%d%d%d%d",&l, &b,&r,&t);l++;b++;r++;t++;printf("%d\n",sum(r, t) - sum(r, b-1) - sum(l-1, t) + sum(l-1, b-1) );}if(op == 3)return 0;}
}

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

快。。。。。

这篇关于【树转数组】poj1195的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---