- 浏览: 599963 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.
通常对一维数组最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.
一、回顾一维树状数组
假设一维数组为A[i](i=1,2,...n),则与它对应的树状数组C[i](i=1,2,...n)是这样定义的:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
(1)C[t]展开以后有多少项?由下面公式计算:
int lowbit(int t){//计算c[t]展开的项数
return t&(-t);
}
C[t]展开的项数就是lowbit(t),C[t]就是从A[t]开始往左连续求lowbit(t)个数的和.
(2)修改
比如修改了A3,必须修改C3,C4,C8,C16,C32,C64...
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
//给A[i]加上 x后,更新一系列C[j]
(3)求数列A[]的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。
二、树状数组可以扩充到二维。
问题:一个由数字构成的大矩阵,能进行两种操作
1) 对矩阵里的某个数加上一个整数(可正可负)
2) 查询某个子矩阵里所有数字的和,要求对每次查询,输出结果。
一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为:
C[x][y] = ∑ a[i][j], 其中,
x-lowbit(x) + 1 <= i <= x,
y-lowbit(y) + 1 <= j <= y.
例:举个例子来看看C[][]的组成。
设原始二维数组为:
A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},
{a21,a22,a23,a24,a25,a26,a27,a28,a29},
{a31,a32,a33,a34,a35,a36,a37,a38,a39},
{a41,a42,a43,a44,a45,a46,a47,a48,a49}};
那么它对应的二维树状数组C[][]呢?
记:
B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 这是第四行的一维树状数组
那么:
C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,...
这是A[][]第一行的一维树状数组
C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24,
C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,...
这是A[][]数组第一行与第二行相加后的树状数组
C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,...
这是A[][]第三行的一维树状数组
C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,...
这是A[][]数组第一行+第二行+第三行+第四行后的树状数组
搞清楚了二维树状数组C[][]的规律了吗? 仔细研究一下,会发现:
(1)在二维情况下,如果修改了A[i][j]=delta,则对应的二维树状数组更新函数为:
(2)在二维情况下,求子矩阵元素之和∑ a[i][j](前i行和前j列)的函数为
例:测试一下:
未完,待续......
通常对一维数组最直接的算法可以在O(1)时间内完成一次修改,但是需要O(n)时间来进行一次查询.而树状数组的修改和查询均可在O(log(n))的时间内完成.
一、回顾一维树状数组
假设一维数组为A[i](i=1,2,...n),则与它对应的树状数组C[i](i=1,2,...n)是这样定义的:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
……
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
......
(1)C[t]展开以后有多少项?由下面公式计算:
int lowbit(int t){//计算c[t]展开的项数
return t&(-t);
}
C[t]展开的项数就是lowbit(t),C[t]就是从A[t]开始往左连续求lowbit(t)个数的和.
(2)修改
比如修改了A3,必须修改C3,C4,C8,C16,C32,C64...
当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i)
//给A[i]加上 x后,更新一系列C[j]
update(int i,int x){ while(i<=n){ c[i]=c[i]+x; i=i+lowbit(i); } }
(3)求数列A[]的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。
如:Sun(1)=C[1]=A[1]; Sun(2)=C[2]=A[1]+A[2]; Sun(3)=C[3]+C[2]=A[1]+A[2]+A[3]; Sun(4)=C[4]=A[1]+A[2]+A[3]+A[4]; Sun(5)=C[5]+C[4]; Sun(6)=C[6]+C[4]; Sun(7)=C[7]+C[6]+C[4]; Sun(8)=C[8]; ,,,,,, int Sum(int n) //求前n项的和. { int sum=0; while(n>0) { sum+=C[n]; n=n-lowbit(n); } return sum; } lowbit(1)=1 lowbit(2)=2 lowbit(3)=1 lowbit(4)=4 lowbit(5)=1 lowbit(6)=2 lowbit(7)=1 lowbit(8)=8 lowbit(9)=1 lowbit(10)=2 lowbit(11)=1 lowbit(12)=4 lowbit(13)=1 lowbit(14)=2 lowbit(15)=1 lowbit(16)=16 lowbit(17)=1 lowbit(18)=2 lowbit(19)=1 lowbit(20)=4 lowbit(21)=1 lowbit(22)=2 lowbit(23)=1 lowbit(24)=8 lowbit(25)=1 lowbit(26)=2 lowbit(27)=1 lowbit(28)=4 lowbit(29)=1 lowbit(30)=2 lowbit(31)=1 lowbit(32)=32 lowbit(33)=1 lowbit(34)=2 lowbit(35)=1 lowbit(36)=4 lowbit(37)=1 lowbit(38)=2 lowbit(39)=1 lowbit(40)=8 lowbit(41)=1 lowbit(42)=2 lowbit(43)=1 lowbit(44)=4 lowbit(45)=1 lowbit(46)=2 lowbit(47)=1 lowbit(48)=16 lowbit(49)=1 lowbit(50)=2 lowbit(51)=1 lowbit(52)=4 lowbit(53)=1 lowbit(54)=2 lowbit(55)=1 lowbit(56)=8 lowbit(57)=1 lowbit(58)=2 lowbit(59)=1 lowbit(60)=4 lowbit(61)=1 lowbit(62)=2 lowbit(63)=1 lowbit(64)=64
二、树状数组可以扩充到二维。
问题:一个由数字构成的大矩阵,能进行两种操作
1) 对矩阵里的某个数加上一个整数(可正可负)
2) 查询某个子矩阵里所有数字的和,要求对每次查询,输出结果。
一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为:
C[x][y] = ∑ a[i][j], 其中,
x-lowbit(x) + 1 <= i <= x,
y-lowbit(y) + 1 <= j <= y.
例:举个例子来看看C[][]的组成。
设原始二维数组为:
A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},
{a21,a22,a23,a24,a25,a26,a27,a28,a29},
{a31,a32,a33,a34,a35,a36,a37,a38,a39},
{a41,a42,a43,a44,a45,a46,a47,a48,a49}};
那么它对应的二维树状数组C[][]呢?
记:
B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 这是第四行的一维树状数组
那么:
C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,...
这是A[][]第一行的一维树状数组
C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24,
C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,...
这是A[][]数组第一行与第二行相加后的树状数组
C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,...
这是A[][]第三行的一维树状数组
C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,...
这是A[][]数组第一行+第二行+第三行+第四行后的树状数组
搞清楚了二维树状数组C[][]的规律了吗? 仔细研究一下,会发现:
(1)在二维情况下,如果修改了A[i][j]=delta,则对应的二维树状数组更新函数为:
private void Modify(int i, int j, int delta){ A[i][j]+=delta; for(int x = i; x< A.length; x += lowbit(x)) for(int y = j; y <A[i].length; y += lowbit(y)){ C[x][y] += delta; } }
(2)在二维情况下,求子矩阵元素之和∑ a[i][j](前i行和前j列)的函数为
int Sum(int i, int j){ int result = 0; for(int x = i; x > 0; x -= lowbit(x)) { for(int y = j; y > 0; y -= lowbit(y)) { result += C[x][y]; } } return result; } 比如: Sun(1,1)=C[1][1]; Sun(1,2)=C[1][2]; Sun(1,3)=C[1][3]+C[1][2];... Sun(2,1)=C[2][1]; Sun(2,2)=C[2][2]; Sun(2,3)=C[2][3]+C[2][2];... Sun(3,1)=C[3][1]+C[2][1]; Sun(3,2)=C[3][2]+C[2][2];
例:测试一下:
import java.util.Arrays; public class Test{ int[][] A;//原二维数组 int[][] C;//对应的二维树状数组 public Test(){ A=new int[5][6]; C=new int[5][6]; for(int i=1;i<5;i++) for(int j=1;j<6;j++) Modify(i,j,1);//给A[][]每个元素加1 for(int i=1;i<5;i++){ for(int j=1;j<6;j++) System.out.print(A[i][j]+" ");//输出A[][] System.out.println(); } System.out.println(Sum(3,4));//求子二维数组的和 Modify(2,3,4);//将A[2][3]加4 System.out.println(Sum(3,4));//显示修改后的和 } private int lowbit(int t){ return t&(-t); } int Sum(int i, int j){ int result = 0; for(int x = i; x > 0; x -= lowbit(x)) { for(int y = j; y > 0; y -= lowbit(y)) { result += C[x][y]; } } return result; } private void Modify(int i, int j, int delta){ A[i][j]+=delta; for(int x = i; x< A.length; x += lowbit(x)) for(int y = j; y <A[i].length; y += lowbit(y)){ C[x][y] += delta; } } public static void main(String args[]){ Test t=new Test(); } } C:\java>java Test 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 16
未完,待续......
- Test777777.zip (570 Bytes)
- 下载次数: 1
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2389北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1984import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1885POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1395接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1818关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1803关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1816关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1769一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2090POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2567设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2111继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2541继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2690先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2286一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2060形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2849例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2126字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18696堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4043一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3328前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
用 for 循环产生 4 行 100 列二维数组,数组成员如下: 1,2,3………100 100,99,98………..1 6,7,8………….105 105,104,103………6 从这个数组中提取出 2 行 50 列的二维数组,成员如下: 50,49,48……...
二维树状数组,又称2D线段树,是数据结构中的一个重要概念,主要应用于解决二维区间查询和修改问题。在ACM(国际大学生程序设计竞赛)中,这种数据结构经常被用来提高算法的效率,特别是在处理动态维护区间信息的...
题目:1 用for循环产生4行100列的二维数组,数组成员如下: 1,2,3.......100; 100,99,98.......1; 6,7,8.......105; 105,104,103......6; 从这个数组中提取2行50列的二维数组,数组成员如下: 50,49,48......1; 56,57,58....
用数组创建函数创建一个二维数组显示件,成员为: 4 5 6 1 2 3 3 4 5 6 1 2 2 3 4 5 6 1 1 2 3 4 5 6 编程将上述创建的数组转置为: 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 1 5 6 1 2 6 1 2 3
本文将详细讲解易语言中二维数组的赋值方法,并通过实例源码帮助你深入理解这一概念。 二维数组,顾名思义,是具有两个索引维度的数组,可以看作是由若干个一维数组排列而成的一个矩形阵列。在易语言中,二维数组...
一维数组转二维数组
1. **一维数组**:一维数组是线性数据结构,可以看作是一系列相同类型元素的集合。声明一维数组时,需要指定数组的类型和大小。例如,`int arr[10]` 定义了一个包含10个整数的一维数组。 2. **二维数组**:二维数组...
在易语言中,二维数组是数组的一种变体,它可以理解为多个一维数组的组合,常用于处理表格或者矩阵类的数据。本篇文章将深入探讨易语言中的二维数组赋值以及相关源码解析。 首先,了解易语言的基本语法对于学习二维...
将labview内二维数组方便的转化为一维数组使用
本学习笔记将深入探讨如何在LabVIEW中实现对二维数组的搜索匹配,特别是针对字符串类型的二维数组。由于LabVIEW内建的函数库并未直接提供搜索二维数组的功能,我们需要自定义方法来解决这个问题。 首先,我们需要...
一维数组可以看作是一条直线上的元素集合,而二维数组则可以理解为一个矩阵,它由多个一维数组组成,每个一维数组代表一行。在C#中,定义一维数组的语法如下: ```csharp int[] oneDimensionalArray = new int[5]; ...
在C语言中,二维数组是处理表格数据的一种基础方式,它本质上是一组一维数组的集合,每个一维数组代表数组的一行。本编程练习旨在加深对C语言中二维数组、指针和函数的理解,通过实际操作提升编程技能。下面我们将...
在LabVIEW编程环境中,二维数组是一种常见的数据结构,用于存储多行多列的数据。本教程将深入探讨如何在LabVIEW中有效地读取二维数组的所有数据,这对于数据分析、处理和可视化至关重要。 首先,让我们理解二维数组...
对于二维数组的排序,通常的做法是先将其转换为一维数组,然后再利用冒泡排序对一维数组进行排序,最后再将排序后的一维数组还原为二维数组。这种方法不仅易于理解和实现,而且能够充分利用已有的排序算法。 1. **...
在C#编程中,动态二维数组是一种非常重要的数据结构,特别是在处理不定数量的数据或需要灵活扩展数据表的情况下。本文将深入探讨动态二维数组的概念、创建方法、操作技巧以及其在实际编程中的应用。 动态二维数组,...
C# json 一维数组 和 二维数组的转换 写的非常详细,对大家有帮助
理解并熟练掌握一维数组、二维数组和三维数组的概念及其操作是学习更高级数据结构和算法的基础。在C++中,利用模板可以创建更灵活的数组结构,适应不同的需求。通过深入研究这些概念,开发者将能够更好地处理和分析...