poj1195 mobile phones 【二维树状数组】

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

一次AC

二维树状数组，有模版很好办

注意二维树状数组这个下标是[1][1]的

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int Max = 1030;
int row, col, ar[Max][Max];
//  二维的其实下标为[1][1]，这个要记得。
int lowbit(int x)
{return x & (-x);
}void add(int i, int j, int w)
{int tmpj;while(i <= row){tmpj = j;while(tmpj <= col){ar[i][tmpj] += w;tmpj += lowbit(tmpj);}i += lowbit(i);}
}int sum(int i, int j)
{int tmpj, ans = 0;while(i > 0){tmpj = j;while(tmpj > 0){ans += ar[i][tmpj];tmpj -= lowbit(tmpj);}i -= lowbit(i);}return ans;
}int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifint tmp,n;scanf("%d%d",&tmp,&n);row=col=n;while(true){int kind,x,y,xx,yy,v;scanf("%d",&kind);if(kind==1){scanf("%d%d%d",&x,&y,&v);add(x+1,y+1,v);}else if(kind==2){scanf("%d%d%d%d",&x,&y,&xx,&yy);x++;y++;xx++;yy++;printf("%d\n",sum(xx,yy)-sum(xx,y-1)-sum(x-1,yy)+sum(x-1,y-1));}else{break;}}return 0;
}

 

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

---