POJ1195 Mobile phones（二维树状数组）
source link: https://arminli.com/poj1195/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
POJ1195 Mobile phones（二维树状数组）
February 15, 2016
题意：给定矩阵，对点更新，询问给两个点，求这两个点构成矩形内元素和。
二维数组可以对点更新，sum 求的是（1，1）到（x，y）的和。
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[1050][1050];
int lowbit(int x){
return x&(-x);
}
void add2(int x,int y,int num){
for(int i = x; i <= n; i += lowbit(i))
for(int j = y; j <= n; j += lowbit(j))
a[i][j] += num;
}
int sum2(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(){
//freopen("a.txt", "r", stdin);
int x,y,w,xx,yy,q;
scanf("%d%d", &q, &n);
memset(a, 0, sizeof(a));
while(scanf("%d", &q) && q<3){
if(q==1){
scanf("%d%d%d", &x, &y, &w);
add2(++x, ++y, w);
}else if(q==2){
scanf("%d%d%d%d", &x, &y, &xx, &yy);
x++;y++;xx++;yy++;
printf("%dn", sum2(xx,yy)-sum2(x-1,yy)-sum2(xx,y-1)+sum2(x-1,y-1));
}
}
return 0;
}
Recommend
-
65
-
21
简介 树状数组和下面的线段树可是亲兄弟了，但他俩毕竟还有一些区别： 树状数组能有的操作，线段树一定有； 线段树有的操作，树状数组不一定有。 这么看来选择线段树 不就 「得天下了」...
-
37
学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是 \(O(logN)\) 级别的数据结构的美，但是做起题来还是相当痛苦的（特别是一开始只会模板的时候，很难灵活运用线段树的性质）。还好有雨巨大神带入门，视频讲...
-
10
【小算法】将数组处理成树状结构 2021年4月8日 96次浏览 将数组处理成树状结构，也是在工作中经常遇到的，今天就和大家一起分享一下思路和方法。 如下代码，处理成树状结构，要求程序具有容错能力，也就是可以判断输...
-
10
POJ2155 Matrix（二维树状数组）February 15, 2016题目链接 题意：矩阵默认全为 0，操作是对输入的两个点构成的矩形内所有元素取反，询问是问某个点是 1 还是 0。 二维树状数组解...
-
10
NEU1686 Sort（DP 树状数组）February 15, 2016题目链接 题意：题目比较难懂，复制讨论版的内容，为第二个样例的分析： As we know, there are 27 kinds of p...
-
13
Armin's BlogPOJ2299 Ultra-QuickSort（离散化 树状数组）February 14, 2016题目链接 题意：求 n 个数的逆序对数。 思路：首先 n 只有 500000...
-
16
Armin's BlogNEU1438 Car race game（树状数组）February 17, 2016题目链接 题意：在一维坐标轴上给出 n 个人的起点和速度，问一...
-
4
UESTC1217 The Battle of Chibi（DP 树状数组）February 15, 2016题目链接 题意：从 n 个数中找出 m 个数，满足严格递增，问能找出几个序列。 思路：dp[i][j]表示以...
-
15
poj 2155 Matrix (二维树状数组) 2013-08-31 分类：未分类 阅读(4293) 评论(0) ...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK