精华内容
下载资源
问答
  • 树状数组

    2017-06-15 12:11:00
    ,最最简单方法就是每次进行计算,但是这需要O(N)时间复杂度,如这个需求非常频繁,那么这个操作就会占用大量CPU时间,进一步想一想,你有可能会想到使用空间换取时间方法,把每一段区间值一次记录下来...

    在一个数组中。若你需要频繁的计算一段区间内的和,你会怎么做?,最最简单的方法就是每次进行计算,但是这需要O(N)的时间复杂度,如这个需求非常的频繁,那么这个操作就会占用大量的CPU时间,进一步想一想,你有可能会想到使用空间换取时间的方法,把每一段区间的值一次记录下来,然后存储在内存中,将时间复杂度降低到O(1),的确,对于目前的这个需求来说,已经能够满足时间复杂度上的要求,尽管带来了线性空间复杂度的提升.

    但若是我们的源数据需要频繁的更改怎么办?使用上面的方案,我们需要大量的更新我们保存到内存中的区间和,而且这中间的很多更新的影响是重叠的,我们需要重复计算。例如对于数组array[10],更新了array[4]值,需要更新区间[4,5],[4,5,6],在更新[4,5,6]需要又一次的计算[4,5],这样的更新带来了非常多的重复计算,为了解决这一问题,树状数组应运而生了。

    当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.树状数组是一种非常优雅的数据结构.先来看看一张树状结构的图片

    QQ截图未命名1 

    图中C[1]的值等于A[1],C[2]的值等于C[1]+A[2]=A[1]+a[2],C[4]的值=C[2]+C[3]=A[1]+A[2]+A[3]+A[4],假设我们现在需要更改元素a[2],那么它将只影响到得c数组中的元素有c[2],c[4],c[8],我们只需要重新计算这几个值即可,减少了很多重复的操作。这就是树状结构大致的一个存贮示意图,下面看看他的定义:

    假设a[1...N]为原数组,定义c[1...N]为对应的树状数组:

    c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i] (其中k为i的二进制表示末尾0的个数)

    下面枚举出i由1...5的数据,可见正是因为上面的a[i - 2^k + 1]...a[i]的计算公式保证了我们C数组的正确意义,至于证明过程,大家可以翻阅相关资料..

    image

    基本操作:

    对于C[i]=a[i - 2^k + 1]...a[i]的定义中,比较难以逐磨的k,他的值等于i这个数的二进制表示末尾0的个数.如4的二进制表示0100,此时k就等于2,而实际上我们还会发现2^k就是前一位的权值,即0100中,2^2=4,刚好是前一位数1的权值.所以所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n),例如:

    为了表示简便,假设现在一个int型为4位,最高位为符号位

    int i=3&(-3);     此时i=1,3的二进制为0011,-3的二进制为1101(负数存的是补码)所以0011&1101=1

    int j=4&(-4);    此时j=4,理由同上..

    所以计算2^k我们可以用如下代码:

     

    1 int lowbit(int x)//计算lowbit 
    2 { 
    3     return x&(-x); 
    4 }

     

    求和操作:

    在上面的示意图中,若我们需要求sum[1..7]个元素的和,仅需要计算c[7]+c[6]+c[4]的和即可,究竟时间复杂度怎么算呢?一共要进行多少次求和操作呢?

    求sum[1..k],我们需查找k的二进制表示中1的个数次就能得到最终结果,具体为什么,请见代码i-=lowbit(i)注释

     

    复制代码
     1 int sum(int i)//求前i项和 
     2 { 
     3     int s=0; 
     4     while(i>0) 
     5     { 
     6         s+=c[i]; 
     7         i-=lowbit(i); //这一步实际上等价于将i的二进制表示的最后一个1剪去,再向前数当前1的权个数(例子在下面),
     8                       //而n的二进制里最多有log(n)个1,所以查询效率是log(n)
     9                       //在示意图上的操作即可理解为依次找到所有的子节点
    10     } 
    11     return s; 
    12 }
    复制代码

     

    以求sum[1..7]为例,二进制为0111,右边第一个1出现在第0位上,也就是说要从a[7]开始向前数1个元素(只有a[7]),即c[7];

    然后将这个1舍掉,得到6,二进制表示为0110,右边第一个1出现在第1位上,也就是说要从a[6]开始向前数2个元素(a[6],a[5]),即c[6];

    然后舍掉用过的1,得到4,二进制表示为0100,右边第一个1出现在第2位上,也就是说要从a[4]开始向前数4个元素(a[4],a[3],a[2],a[1]),即c[4].

    所以s[7]=c[7]+c[6]+c[4]

    给源数组加值操作:

    在上面的示意图中,假设更改的元素是a[2],那么它影响到得c数组中的元素有c[2],c[4],c[8],我们只需一层一层往上修改就可以了,这个过程的最坏的复杂度也不过O(logN);

     

    复制代码
    void add(int i,int val) 

        while(i<=n) 
        { 
            c[i]+=val; 
            i+=lowbit(i); //i+(i的二进制中最后一个1的权值,即2^k),在示意图上的操作即为提升一层,到上一层的节点.
                               //这个过程实际上也只是一个把末尾1后补0的过程(例子在下面) 
        } 
    }
    复制代码

     

    以修改a[2]元素为例,需要修改c[2],2的二进制为0010,末尾补0为0100,即c[4]

    4的二进制为0100,在末尾补0为1000即c[8]。所以我们需要修改的有c[2],c[4],c[8]

     

    POJ上面有一个这方面的水题,可以帮助理解  http://poj.org/problem?id=2352

    解题报告http://hi.baidu.com/acmerskycoding/blog/item/40af1b2585dd310a4c088d95.html

     在一个数组中。若你需要频繁的计算一段区间内的和,你会怎么做?,最最简单的方法就是每次进行计算,但是这需要O(N)的时间复杂度,如这个需求非常的频繁,那么这个操作就会占用大量的CPU时间,进一步想一想,你有可能会想到使用空间换取时间的方法,把每一段区间的值一次记录下来,然后存储在内存中,将时间复杂度降低到O(1),的确,对于目前的这个需求来说,已经能够满足时间复杂度上的要求,尽管带来了线性空间复杂度的提升.

    但若是我们的源数据需要频繁的更改怎么办?使用上面的方案,我们需要大量的更新我们保存到内存中的区间和,而且这中间的很多更新的影响是重叠的,我们需要重复计算。例如对于数组array[10],更新了array[4]值,需要更新区间[4,5],[4,5,6],在更新[4,5,6]需要又一次的计算[4,5],这样的更新带来了非常多的重复计算,为了解决这一问题,树状数组应运而生了。

    当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.树状数组是一种非常优雅的数据结构.先来看看一张树状结构的图片

    QQ截图未命名1 

    图中C[1]的值等于A[1],C[2]的值等于C[1]+A[2]=A[1]+a[2],C[4]的值=C[2]+C[3]=A[1]+A[2]+A[3]+A[4],假设我们现在需要更改元素a[2],那么它将只影响到得c数组中的元素有c[2],c[4],c[8],我们只需要重新计算这几个值即可,减少了很多重复的操作。这就是树状结构大致的一个存贮示意图,下面看看他的定义:

    假设a[1...N]为原数组,定义c[1...N]为对应的树状数组:

    c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i] (其中k为i的二进制表示末尾0的个数)

    下面枚举出i由1...5的数据,可见正是因为上面的a[i - 2^k + 1]...a[i]的计算公式保证了我们C数组的正确意义,至于证明过程,大家可以翻阅相关资料..

    image

    基本操作:

    对于C[i]=a[i - 2^k + 1]...a[i]的定义中,比较难以逐磨的k,他的值等于i这个数的二进制表示末尾0的个数.如4的二进制表示0100,此时k就等于2,而实际上我们还会发现2^k就是前一位的权值,即0100中,2^2=4,刚好是前一位数1的权值.所以所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n),例如:

    为了表示简便,假设现在一个int型为4位,最高位为符号位

    int i=3&(-3);     此时i=1,3的二进制为0011,-3的二进制为1101(负数存的是补码)所以0011&1101=1

    int j=4&(-4);    此时j=4,理由同上..

    所以计算2^k我们可以用如下代码:

     

    1 int lowbit(int x)//计算lowbit 
    2 { 
    3     return x&(-x); 
    4 }

     

    求和操作:

    在上面的示意图中,若我们需要求sum[1..7]个元素的和,仅需要计算c[7]+c[6]+c[4]的和即可,究竟时间复杂度怎么算呢?一共要进行多少次求和操作呢?

    求sum[1..k],我们需查找k的二进制表示中1的个数次就能得到最终结果,具体为什么,请见代码i-=lowbit(i)注释

     

    复制代码
     1 int sum(int i)//求前i项和 
     2 { 
     3     int s=0; 
     4     while(i>0) 
     5     { 
     6         s+=c[i]; 
     7         i-=lowbit(i); //这一步实际上等价于将i的二进制表示的最后一个1剪去,再向前数当前1的权个数(例子在下面),
     8                       //而n的二进制里最多有log(n)个1,所以查询效率是log(n)
     9                       //在示意图上的操作即可理解为依次找到所有的子节点
    10     } 
    11     return s; 
    12 }
    复制代码

     

    以求sum[1..7]为例,二进制为0111,右边第一个1出现在第0位上,也就是说要从a[7]开始向前数1个元素(只有a[7]),即c[7];

    然后将这个1舍掉,得到6,二进制表示为0110,右边第一个1出现在第1位上,也就是说要从a[6]开始向前数2个元素(a[6],a[5]),即c[6];

    然后舍掉用过的1,得到4,二进制表示为0100,右边第一个1出现在第2位上,也就是说要从a[4]开始向前数4个元素(a[4],a[3],a[2],a[1]),即c[4].

    所以s[7]=c[7]+c[6]+c[4]

    给源数组加值操作:

    在上面的示意图中,假设更改的元素是a[2],那么它影响到得c数组中的元素有c[2],c[4],c[8],我们只需一层一层往上修改就可以了,这个过程的最坏的复杂度也不过O(logN);

     

    复制代码
    void add(int i,int val) 

        while(i<=n) 
        { 
            c[i]+=val; 
            i+=lowbit(i); //i+(i的二进制中最后一个1的权值,即2^k),在示意图上的操作即为提升一层,到上一层的节点.
                               //这个过程实际上也只是一个把末尾1后补0的过程(例子在下面) 
        } 
    }
    复制代码

     

    以修改a[2]元素为例,需要修改c[2],2的二进制为0010,末尾补0为0100,即c[4]

    4的二进制为0100,在末尾补0为1000即c[8]。所以我们需要修改的有c[2],c[4],c[8]

     

    转载于:https://www.cnblogs.com/zhangyubao/p/7016908.html

    展开全文
  • 树状数组详解

    2015-04-02 11:52:55
    ,最最简单方法就是每次进行计算,但是这需要O(N)时间复杂度,如这个需求非常频繁,那么这个操作就会占用大量CPU时间,进一步想一想,你有可能会想到使用空间换取时间方法,把每一段区间值一次记录下来...

    在一个数组中。若你需要频繁的计算一段区间内的和,你会怎么做?,最最简单的方法就是每次进行计算,但是这需要O(N)的时间复杂度,如这个需求非常的频繁,那么这个操作就会占用大量的CPU时间,进一步想一想,你有可能会想到使用空间换取时间的方法,把每一段区间的值一次记录下来,然后存储在内存中,将时间复杂度降低到O(1),的确,对于目前的这个需求来说,已经能够满足时间复杂度上的要求,尽管带来了线性空间复杂度的提升.

    但若是我们的源数据需要频繁的更改怎么办?使用上面的方案,我们需要大量的更新我们保存到内存中的区间和,而且这中间的很多更新的影响是重叠的,我们需要重复计算。例如对于数组array[10],更新了array[4]值,需要更新区间[4,5],[4,5,6],在更新[4,5,6]需要又一次的计算[4,5],这样的更新带来了非常多的重复计算,为了解决这一问题,树状数组应运而生了。

    当要频繁的对数组元素进行修改,同时又要频繁的查询数组内任一区间元素之和的时候,可以考虑使用树状数组.树状数组是一种非常优雅的数据结构.先来看看一张树状结构的图片

    QQ截图未命名1 

    图中C[1]的值等于A[1],C[2]的值等于C[1]+A[2]=A[1]+a[2],C[4]的值=C[2]+C[3]=A[1]+A[2]+A[3]+A[4],假设我们现在需要更改元素a[2],那么它将只影响到得c数组中的元素有c[2],c[4],c[8],我们只需要重新计算这几个值即可,减少了很多重复的操作。这就是树状结构大致的一个存贮示意图,下面看看他的定义:

    假设a[1...N]为原数组,定义c[1...N]为对应的树状数组:

    c[i] = a[i - 2^k + 1] + a[i - 2^k + 2] + ... + a[i] (其中k为i的二进制表示末尾0的个数)

    下面枚举出i由1...5的数据,可见正是因为上面的a[i - 2^k + 1]...a[i]的计算公式保证了我们C数组的正确意义,至于证明过程,大家可以翻阅相关资料..

    image

    基本操作:

    对于C[i]=a[i - 2^k + 1]...a[i]的定义中,比较难以逐磨的k,他的值等于i这个数的二进制表示末尾0的个数.如4的二进制表示0100,此时k就等于2,而实际上我们还会发现2^k就是前一位的权值,即0100中,2^2=4,刚好是前一位数1的权值.所以所以2^k可以表示为n&(n^(n-1))或更简单的n&(-n),例如:

    为了表示简便,假设现在一个int型为4位,最高位为符号位

    int i=3&(-3);     此时i=1,3的二进制为0011,-3的二进制为1101(负数存的是补码)所以0011&1101=1

    int j=4&(-4);    此时j=4,理由同上..

    所以计算2^k我们可以用如下代码:

     

    1 int lowbit(int x)//计算lowbit 
    2 
    3     return x&(-x); 
    4 }

     

    求和操作:

    在上面的示意图中,若我们需要求sum[1..7]个元素的和,仅需要计算c[7]+c[6]+c[4]的和即可,究竟时间复杂度怎么算呢?一共要进行多少次求和操作呢?

    求sum[1..k],我们需查找k的二进制表示中1的个数次就能得到最终结果,具体为什么,请见代码i-=lowbit(i)注释

     

    复制代码
     1 int sum(int i)//求前i项和 
     2 
     3     int s=0
     4     while(i>0
     5     { 
     6         s+=c[i]; 
     7         i-=lowbit(i); //这一步实际上等价于将i的二进制表示的最后一个1剪去,再向前数当前1的权个数(例子在下面),
     8                       //而n的二进制里最多有log(n)个1,所以查询效率是log(n)
     9                       //在示意图上的操作即可理解为依次找到所有的子节点
    10     } 
    11     return s; 
    12 }
    复制代码

     

    以求sum[1..7]为例,二进制为0111,右边第一个1出现在第0位上,也就是说要从a[7]开始向前数1个元素(只有a[7]),即c[7];

    然后将这个1舍掉,得到6,二进制表示为0110,右边第一个1出现在第1位上,也就是说要从a[6]开始向前数2个元素(a[6],a[5]),即c[6];

    然后舍掉用过的1,得到4,二进制表示为0100,右边第一个1出现在第2位上,也就是说要从a[4]开始向前数4个元素(a[4],a[3],a[2],a[1]),即c[4].

    所以s[7]=c[7]+c[6]+c[4]

    给源数组加值操作:

    在上面的示意图中,假设更改的元素是a[2],那么它影响到得c数组中的元素有c[2],c[4],c[8],我们只需一层一层往上修改就可以了,这个过程的最坏的复杂度也不过O(logN);

     

    复制代码
    void add(int i,int val) 

        
    while(i<=n) 
        { 
            c[i]
    +=val; 
            i
    +=lowbit(i); //i+(i的二进制中最后一个1的权值,即2^k),在示意图上的操作即为提升一层,到上一层的节点.
                               //这个过程实际上也只是一个把末尾1后补0的过程(例子在下面) 
        } 
    }
    复制代码

     

    以修改a[2]元素为例,需要修改c[2],2的二进制为0010,末尾补0为0100,即c[4]

    4的二进制为0100,在末尾补0为1000即c[8]。所以我们需要修改的有c[2],c[4],c[8]

     

    展开全文
  • 书中列出了C用户经常问400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面主题,并分别给出了解答,而且结合代码示例阐明要点。 本书结构清晰,讲解透彻,是各高校相关...
  • 6.23 sizeof返回大小是以字节计算的,怎样才能判断数组中有多少个元素呢?  第7章 内存分配  基本内存分配问题  7.1 为什么这段代码不行?char*answer;printf("Typesomething:\n");gets(answer);printf(...
  • 6.23 sizeof返回大小是以字节计算的,怎样才能判断数组中有多少个元素呢? 第7章 内存分配 基本内存分配问题 7.1 为什么这段代码不行?char*answer;printf("Typesomething:\n");gets(answer);printf(...
  •  存储类型 1.10 同一个静态(static)函数或变量所有声明都必须包含static存储类型吗? 1.11 extern在函数声明中是什么意思? 1.12 关键字auto到底有什么用途? 类型定义(typedef) 1.13 对于用户定义类型,...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    书中列出了C用户经常问400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预处理器等各个方面主题,并分别给出了解答,而且结合代码示例阐明要点。 《你必须知道495个C语言问题》结构...
  • 例如定义一个包含N个指向返回指向字符指针函数指针的数组? 11  1.22 如何声明返回指向同类型函数指针函数?我在设计一个状态机,用函数表示每种状态,每个函数都会返回一个指向下一个状态函数指针...
  • key、散列函数、value, key 通过散列函数计算得到 value 存储的位置</li><li>设计散列函数</li><li>控制散列表装载因子,初始大小和动态扩容策略</li><li>有效解决散列冲突</li><li>对一个工业级散列表...
  • c++ 面试题 总结

    2009-09-16 08:44:40
    页式管理:把主存分为一页一页,每一页的空间要比一块一块的空间小很多,显然这种方法的空间利用率要比块式管理高很多。 段式管理:把主存分为一段一段,每一段的空间又要比一页一页的空间小很多,这种方法在...
  • 5.5串的存储结构 128 感情上发生了问题,为了向女友解释一下,我准备发一条短信,一共打了75个字。最后八个字是“我恨你是不可能的”,点发送。后来得知对方收到的,只有70个字,短信结尾是“……我恨你”。 5.5.1串...
  • 6.7二叉树的存储结构 172 6.7.1二叉树顺序存储结构 172 6.7.2二叉链表 173 6.8遍历二叉树 174 你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由于选择方式的不同,遍历的次序就完全不同。 ...
  • 3.1.6 C中变量的存储类型有哪些? 3.1.7 动态规划的本质 3.1.8 实践中如何优化MySQL? 3.1.9 什么情况下设置了索引但无法使用? 3.2.0 SQL语句的优化 3.2.1 数据库索引的底层实现原理和优化 3.2.2 HTTP和HTTPS的...
  • 大话数据结构

    2019-01-10 16:35:22
    6.7二叉树的存储结构 172 6.7.1二叉树顺序存储结构 172 6.7.2二叉链表 173 6.8遍历二叉树 174 你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由于选择方式的不同,遍历的次序就完全不同。 ...
  • 在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。 (3)从堆上分配,亦称动态内存分配。...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    6.7二叉树的存储结构 172 6.7.1二叉树顺序存储结构 172 6.7.2二叉链表 173 6.8遍历二叉树 174 你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由于选择方式的不同,遍历的次序就完全不同。 ...
  • 2.11 最坏情况与平均情况 35 2.12 算法空间复杂度 36 事先建立一个有2050大的数组,然后把所有年份按下标数字对应,如果是闰年,此数组值就是1,如果不是就是0。这样,所谓判断某一年是否是闰年就变成了查找...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    6.7 二叉树的存储结构 172 6.7.1 二叉树顺序存储结构 172 6.7.2 二叉链表 173 6.8 遍历二叉树 174 你人生的道路上,高考填志愿要面临哪个城市、哪所大学、具体专业等选择,由于选择方式的不同,遍历的次序就完全...
  • java 面试题 总结

    2009-09-16 08:45:34
    7、说出ArrayList,Vector, LinkedList的存储性能和特性 ArrayList和Vector都是使用数组方式存储数据,此数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组...
  • C++程序员面试宝典

    热门讨论 2013-04-01 13:36:19
    面试题80 如何分配和释放存储空间 84 7.4 虚函数与纯虚函数 85 面试题81 虚函数与纯虚函数区别 85 面试题82 如何使用纯虚函数 86 第8章 指针(教学视频:60分钟) 88 8.1 指针概述 88 面试题83 什么是指针 88 面试...
  • 在Js中数组可以存储任意数据,而且它大小是可以动态调整类似于OC中NSMutableArray。创建数组可以使用构造函数方式也可以使用字面量形式,另外可以使用concat从一个数组中复制一个副本出来。...
  • 可靠Windows版Redis-教你怎么解决64位Windows版Redis狂占C盘问题 Oracle中 SQL 执行太慢元凶: OR Windows下载安装JDK【废弃】 小伙伴书三生 2014年 排斥所有液体新型超疏水纳米材料 20纳米DDR4内存 ...

空空如也

空空如也

1 2
收藏数 26
精华内容 10
关键字:

怎么计算数组占用的存储空间