- 浏览: 601177 次
- 来自: ...
文章分类
最新评论
-
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 2394北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1986import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1893POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1395接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1822关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1814关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1817关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1773一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2099POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2574设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2116继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2542继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2701先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2290一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2061形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2850例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2133字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18705堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4044一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3329前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
在本篇中,我们将深入学习二维树状数组的应用,并通过解决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维.txt"和"2维.txt"文件中,应该包含了一维和二维树状数组的具体实现代码,你可以通过阅读这些源码来深入理解它们的工作原理和细节。学习和掌握树状数组对于解决动态规划、区间查询和更新等问题非常有帮助...
题目: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. **二维数组**:二维数组...
在易语言中,二维数组是数组的一种变体,它可以理解为多个一维数组的组合,常用于处理表格或者矩阵类的数据。本篇文章将深入探讨易语言中的二维数组赋值以及相关源码解析。 首先,了解易语言的基本语法对于学习二维...
一维数组可以理解为一个行或列,而二维数组则类似于表格,由多个行和列组成。本案例"使用Excel两个一维数组构造二维数组.rar"重点讲解如何通过Excel的数组公式,将两个一维数组合并成一个二维数组,并进行加法运算。...
将labview内二维数组方便的转化为一维数组使用
本学习笔记将深入探讨如何在LabVIEW中实现对二维数组的搜索匹配,特别是针对字符串类型的二维数组。由于LabVIEW内建的函数库并未直接提供搜索二维数组的功能,我们需要自定义方法来解决这个问题。 首先,我们需要...
一维数组可以看作是一条直线上的元素集合,而二维数组则可以理解为一个矩阵,它由多个一维数组组成,每个一维数组代表一行。在C#中,定义一维数组的语法如下: ```csharp int[] oneDimensionalArray = new int[5]; ...
在C语言中,二维数组是处理表格数据的一种基础方式,它本质上是一组一维数组的集合,每个一维数组代表数组的一行。本编程练习旨在加深对C语言中二维数组、指针和函数的理解,通过实际操作提升编程技能。下面我们将...
在LabVIEW编程环境中,二维数组是一种常见的数据结构,用于存储多行多列的数据。本教程将深入探讨如何在LabVIEW中有效地读取二维数组的所有数据,这对于数据分析、处理和可视化至关重要。 首先,让我们理解二维数组...
对于二维数组的排序,通常的做法是先将其转换为一维数组,然后再利用冒泡排序对一维数组进行排序,最后再将排序后的一维数组还原为二维数组。这种方法不仅易于理解和实现,而且能够充分利用已有的排序算法。 1. **...
在C#编程中,动态二维数组是一种非常重要的数据结构,特别是在处理不定数量的数据或需要灵活扩展数据表的情况下。本文将深入探讨动态二维数组的概念、创建方法、操作技巧以及其在实际编程中的应用。 动态二维数组,...