首页 > 编程语言 >树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法

树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法

时间：2023-06-02 22:03:33浏览次数：53  
标签：前缀 树状 int self 尼玛 详解 数组 sumRange

 

943. 区间和查询 - Immutable

 

中文

 

English

 

给一个整数数组 nums，求出下标从 i 到 j 的元素和(i ≤ j)，i 跟 j对应的元素也包括在内。

 

样例

样例1

输入: nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2)
sumRange(2, 5)
sumRange(0, 5)
输出:
1
-1
-3
解释: 
sumRange(0, 2) -> (-2) + 0 + 3 = 1
sumRange(2, 5) -> 3 + (-5) + 2 + (-1) = -1
sumRange(0, 5) -> (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

样例2

输入: 
nums = [-4, -5]
sumRange(0, 0)
sumRange(1, 1)
sumRange(0, 1)
sumRange(1, 1)
sumRange(0, 0)
输出: 
-4
-5
-9
-5
-4
解释: 
sumRange(0, 0) -> -4
sumRange(1, 1) -> -5
sumRange(0, 1) -> (-4) + (-5) = -9
sumRange(1, 1) -> -5
sumRange(0, 0) -> -4

 

注意事项

  1. 你可以认为给出的数组不会发生变化。
  2. 会调用非常多次 sumRange 函数。

这题只需要求出给定数组的前缀和数组prefixSum,对于查询[st,ed],输出prefixSum[ed]-prefixSum[st-1]即可

class NumArray:

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.sum = [0]
        for i in nums:
            self.sum += self.sum[-1] + i,

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.sum[j + 1] - self.sum[i]

 

665. 平面范围求和 -不可变矩阵

中文

English

给一 二维矩阵,计算由左上角 (row1, col1) 和右下角 (row2, col2) 划定的矩形内元素和.

样例

样例1

输入：
[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
sumRegion(2, 1, 4, 3)
sumRegion(1, 1, 2, 2)
sumRegion(1, 2, 2, 4)
输出：
8
11
12
解释：
给出矩阵
[
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) = 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8
sumRegion(1, 1, 2, 2) = 6 + 3 + 2 + 0 = 11
sumRegion(1, 2, 2, 4) = 3 + 2 + 1 + 0 + 1 + 5 = 12

样例2

输入：
[[3,0],[5,6]]
sumRegion(0, 0, 0, 1)
sumRegion(0, 0, 1, 1)
输出：
3
14
解释：
给出矩阵
[
  [3, 0],
  [5, 6]
]
sumRegion(0, 0, 0, 1) = 3 + 0 = 3
sumRegion(0, 0, 1, 1) = 3 + 0 + 5 + 6 = 14

注意事项

  1. 你可以假设矩阵不变
  2. 对函数 sumRegion 的调用次数有很多次
  3. 你可以假设 row1 ≤ row2 并且 col1 ≤ col2

不妨设树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法_数组

 

class NumMatrix(object):

    # @param {int[][]} matrix a 2D matrix
    def __init__(self, matrix):
        # Write your code here

        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 
        
        n = len(matrix)
        m = len(matrix[0])
        
        self.dp  = [[0] * (m + 1) for _ in range(n + 1)]
        for r in range(n):
            for c in range(m):
                self.dp[r + 1][c + 1] = self.dp[r + 1][c] + self.dp[r][c + 1] + \
                    matrix[r][c] - self.dp[r][c]

        
    # @param {int} row1 an integer
    # @param {int} col1 an integer
    # @param {int} row2 an integer
    # @param {int} row2 an integer
    # @return {int} the sum of region
    def sumRegion(self, row1, col1, row2, col2):
        # Write your code here
        return self.dp[row2 + 1][col2 + 1] - self.dp[row1][col2 + 1] - \
            self.dp[row2 + 1][col1] + self.dp[row1][col1]

 

840. 可变范围求和

 

中文

 

English

 

给定一个整数数组 nums, 然后你需要实现两个函数:

  • update(i, val) 将数组下标为i的元素修改为val
  • sumRange(l, r) 返回数组下标在树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法_数组_02

 

样例

样例 1:

输入:
  nums = [1, 3, 5]
  sumRange(0, 2)
  update(1, 2)
  sumRange(0, 2)
输出: 
  9
  8

样例 2:

输入: 
  nums = [0, 9, 5, 7, 3]
  sumRange(4, 4)
  sumRange(2, 4)
  update(4, 5)
  update(1, 7)
  update(0, 8)
  sumRange(1, 2)
输出: 
  3
  15
  12

 

注意事项

  1. 数组只能通过update函数进行修改。
  2. 你可以假设 update 函数与 sumRange 函数的调用数量是均匀的。
class NumArray(object):
    
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.arr = nums # 
        self.n = len(nums)
        self.bit = [0] * (self.n + 1)
        for i in range(self.n):
            self.add(i, self.arr[i])

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: void
        """
        self.add(i, val - self.arr[i])
        self.arr[i] = val

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.sum(j) - self.sum(i - 1)
        
    def lowbit(self, x):
        return x & (-x)
    
    def add(self, idx, val):
        idx += 1
        while idx <= self.n:
            self.bit[idx] += val
            idx += self.lowbit(idx)
    
    def sum(self, idx):
        idx += 1
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= self.lowbit(idx)
        return res

 就是使用树状数组来求解。

其中，bit表示Binary Indexed Tree

又名:Fenwick Tree 中文名:树状数组 简写:BIT 基于“前缀和”信息来实现——
Log(n) 修改任意位置值
Log(n) 查询任意区间和

Binary Indexed Tree 事实上就是一个有部分区段累加和数组

 总结在前：

把原先我们累加的方式从:
for (int i = index; i >= 0; i = i - 1) sum += arr[i];
改成了
for (int i = index+1; i >= 1; i = i - lowbit(i)) sum += bit[i];lowbit是核心和关键！！！

树状数组详解

先来看几个问题吧。

1.什么是树状数组？

顾名思义，就是用数组来模拟树形结构呗。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和Trie树的构造方式有类似之处。

2.树状数组可以解决什么问题

可以解决大部分基于区间上的更新以及求和问题。就是上面的算法题目。

3.树状数组和线段树的区别在哪里

树状数组可以解决的问题都可以用线段树解决，这两者的区别在哪里呢？树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+1的问题，但没人会在1+1的问题上用大数模拟。

4.树状数组的优点和缺点

修改和查询的复杂度都是O(logN)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。

缺点是遇到复杂的区间问题还是不能解决，功能还是有限。

一、树状数组介绍

树状数组可以解决什么样的问题：

这里通过一个简单的题目展开介绍，先输入一个长度为n的数组，然后我们有如下两种操作：

  1. 输入一个数m，输出数组中下标1~m的前缀和
  2. 对某个指定下标的数进行值的修改

多次执行上述两种操作

寻常方法
对于一个的数组，如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和，对于n次操作，时间复杂度是O(n^2)，对于值的修改，我们可以直接通过下标找到要修改的数，n次操作时间复杂度为O(n)，在数组n开得比较大的时候，求前缀和的效率显得低了

  • 那么有人提出了一种优化的方式：
    初始我们用一个数组A的保存每个位置的初始值，然后用一个辅助数组B存放的是下标为i的时候A数组的前i个的和（前缀和），那么当我们需要查询m个数的前缀和的时候只要直接使用下标对B数组进行查询即可，n次查询，时间复杂度为O(n)，而此时，对于单点更新值的维护消耗，由原来的O(n)变成了O(n^2)，因为每一次与更新单点值都会对后面的已经计算好的B数组前缀和的值造成影响，需要不断更新B数组的值，n次更新维护的消耗自然就变成了O(n^2)，更新的效率变得低下

树状数组
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢，至少可以令人接受，这里将介绍树状数组如何处理前缀和查询和单点更新的问题，对于n次操作，时间复杂度都为O(nlogn)

树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法_前缀和_03


注意观察箭头高度！！！其中，【1，8】表示sum（a[1~8]）,【5，6】表示sum(a[5~6])

如图，对于一个长度为n的数组，A数组存放的是数组的初始值，引入一个辅助数组C（我们通过C数组建立树状数组）

C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

找规律：

C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i];   //k为i的二进制中从最低位到高位连续零的长度

例如i = 8(1000)时候，k = 3，可自行验证。

 

这个怎么实现求和呢，比如我们要找前7项和，那么应该是SUM = C[7] + C[6] + C[4];

 

树状数组详解——本质上就是空间换时间，可以解决大部分基于区间上的更新以及求和问题 尼玛，专用算法_数组_04

 

我们称C[i]的值为下标为i的数所管辖的数的和，C[8]存放的就是被编号8所管辖的那些数的和（有8个），而下标为i的数所管辖的元素的个数则为2^k个（k为i的二进制的末尾0的个数）举两个例子查询下标m==8和m==5所管辖的数的和

  • 8 = 1000，末尾3个0，故k == 3，所管辖的个数为2^3 == 8，C8是8个数的和
  • 5 = 0101，末尾没有0，故k == 0，所管辖的个数为2^0 == 1，C5是一个数的和（它本身A5）

而对于输入的数m，我们要求编号为m的数的前缀和A1~Am（这里假设树状数组已经建立，即C1~C8的值已经求出，别着急，在本文的最下方会做出建立树状数组的过程讲解，因为现在是在求前缀和，就假设C数组已经可用了吧）举两个例子m==7和m==6（sum(i)表示求编号为i的前缀和）

  • m==7 sum(7) = C7 + C6 + C4
    那么我们是怎么得到编号7是由哪几个C[i]求和得到呢（C4, C6, C7怎么得到的），这里有介绍一种巧妙的方法：
    对于查询的m，将它转换成二进制后，不断对末尾的1的位置进行-1的操作，直到全部为0停止
    7的二进制为0111（C7得到），那么先对0111的末尾1的位置-1，得到0110 == 6（C6得到），再对0110末尾1位置-1，得到0100 == 4（C4得到），最后对0100末尾1位置-1后得到0000（结束信号），计算停止，至此C7，C6，C4全部得到，求和后就是m == 7时它的前缀和
  • m==6 sum(6) = C6 + C4
    m == 6时也是一样，先转成2进制等于0110，经过两次变换后为0100（C4）和0000（结束信号），那么求和后同样也得到了预计的结果

这里要介绍一个高效的方法，lowbit(int m)，这是一个函数，它的作用是求出m的二进制表示的末尾1的位置，对于要查询m的前缀和，m = m - lowbit(m)代表不断对二进制末尾1进行-1操作，不断执行直到m == 0结束，就能得到前缀和由哪几个Cm构成，十分巧妙，lowbit也是树状数组的核心

int lowbit(int m){
    return m&(-m);
}

关于m&(-m)很多童鞋可能感到困惑，那么就不得不提及一下负数在计算机内存中的存储形式，负数在计算机中是以补码的形式存储的，如13的二进制表示为1101，那么-13的二进制而将13二进制按位取反，然后末尾+1，即0010 + 0001 = 0011，那么1101 & 0011== 0001，很显然得到m == 13二进制末尾1的位置是2的0次方位，将13 - 0001 == 12，再对12执行lowbit操作，1100 & 0100 == 0100，也很轻易得到了m == 12时二进制末尾1的位置是2的2次方位，将12 - 0100 == 8，再对8执行lowbit操作，0100 & 1100 == 0100，得到m == 8时二进制位是2的2次方位，8 - 0100 == 0（结束操作），通过循环得到的13，12，8，则sum(13) == C13 + C12 + C8

求前缀和的代码

int ans = 0;
int getSum(int m){
    while(m > 0){
        ans += C[m];
        m -= lowbit(m);
    }
}

对于n次前缀和的查询，时间复杂度为O(nlogn)

接下来讲解单点更新值

对于输入编号为x的值，要求为它的值附加一个value值，我们把图再一次拿下来

假设x==2，value==5，那么我们先找到A[2]的位置，通过观察我们得知，如果修改了A[2]的值，那么管辖A[2]的C[2]，C[4]，C[8]的前缀和都要加上value（所有的祖先节点），那么和查询类似，我们如何得到C2的所有祖先节点呢（因为C2和A2的下标相同所以更新时查询从C[x]开始），依旧是上述的巧妙的方法，但是我们把它倒过来
对于要更新x位置的值，我们把x转换成二进制，不断对二进制最后一个1的位置+1，直到达到数组下标的最大值n结束

  • 对于给出的例子x==2，假设数组下标上限n==8，x转换成二进制后等于0010（C2），对末尾1的位置进行+1，得到0100（C4），对末尾的1的位置进行+1，得到1000（C8），循环结束，对C2，C4，C8的前缀和都要加上value，当然不能忘记对A[2]的值+value，单点更新值过程结束

给出代码

void update(int x, int value){
    A[x] += value;    //不能忘了对A数组进行维护，尽善尽美嘛
    while(x <= n){
        C[x] += value;
        x += lowbit(x);
    }
}

对于n次更新操作，时间复杂度同样为O(nlogn)

这里有一个注意事项，我们对于求前缀和与单点更新时，树状数组C是拿来直接使用的，那么问题来了，树什么时候建立好的，我怎么不知道？?

事实上，对于一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程（把A1~An从0更新成我们输入的A[i]），所以一边读入A[i]，一边将C[i]涉及到的祖先节点值更新，完成输入后树状数组C也就建立成功了

  • 完整代码如下：
#include<stdio.h>
#include<string.h>

int a[10005];
int c[10005];
int n;

int lowbit(int x){
    return x&(-x);
}

int getSum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x, int value){
    a[x] += value;
    while(x <= n){
        c[x] += value;
        x += lowbit(x);
    }
}

int main(){
    while(scanf("%d", &n)!=EOF){    //用于测试n == 8 
        memset(a, 0, sizeof(a));
        memset(c, 0, sizeof(c));
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);     //a[i]的值根据具体题目自己安排测试可以1，2，3，4，5，6，7，8 
            update(i, a[i]);        //输入的过程就是更新的过程 
        }
        int ans = getSum(n-1);      //用于测试输出n-1的前缀和 输出28 
        printf("%d\n", ans);
    }   
    return 0;
}

 

标签：前缀,树状,int,self,尼玛,详解,数组,sumRange
From： https://blog.51cto.com/u_11908275/6405193

相关文章

  • Apollo配置中心管理后台的详解
    上篇【Apollo配置中心源码编译及搭建】搭建了Apollo。这篇来看看怎么使用Apollo管理后台。     Apollo（阿波罗）是携程框架部门研发的开源配置管理中心，能够集中化管理应用不同环境、不同集群的配置，配置修改后能够实时推送到应用端，并且具备规范的权限、流程治理等特性。Apoll......
  • 2014.4.25.12.51_context_2014.4.25_Android种的Context详解
    Android中Context详解----你所不知道的Context一、Context相关类的继承关系2二、什么时候创建Context实例5从上可知一下三点,即：1、它描述的是一个应用程序环境的信息，即上下文。2、该类是一个抽象(abstractclass)类，Android提供了该抽象类的具体实现类(后面我们会讲到是Co......
  • IOS上架流程详解，包含审核避坑指南！
    ​准备开发者账号完工的项目上架步骤一、创建AppID二、创建证书请求文件（CSR文件）三、创建发布证书（CER）四、创建ProvisioningProfiles配置文件（PP文件）五、在AppStore创建应用六、打包上架一、创建AppID1.打开苹果开发者网，点击“Account”登录会员中心 ​......
  • IOS上架流程详解，包含审核避坑指南！
    ​准备开发者账号完工的项目上架步骤一、创建AppID二、创建证书请求文件（CSR文件）三、创建发布证书（CER）四、创建ProvisioningProfiles配置文件（PP文件）五、在AppStore创建应用六、打包上架一、创建AppID1.打开苹果开发者网，点击“Account”登录会员中心 ​......
  • 树状数组讲解与例题 杭电HDU1166，HDU1556，HDU2689
    树状数组的总结树状数组很巧妙地解决了数列的求和与查找，速度很快。树状数组，它改变数列中某一位，或者求某个区间的和，时间复杂度是O（logN）；效率大为改善。下面的图片很好的演示了树状数组的存储原理。（图片来自网络）观察图片，会发现：数组c的每一个元素都管辖着一定范围内的数组a元素的和，比如C......
  • HDU 5542 The Battle of Chibi（树状数组+dp）
    TheBattleofChibiTimeLimit:6000/4000MS(Java/Others)    MemoryLimit:65535/65535K(Java/Others)TotalSubmission(s):1749    AcceptedSubmission(s):621ProblemDescriptionCaoCaomadeupabigarmyandwasgoingtoinvadethewholeSou......
  • ICPC2017网络赛（南宁）子序列最大权值（树状数组+dp）
    https://nanti.jisuanke.com/t/17319LetSSbeasequenceofintegerss_{1}s1,s_{2}s2,......,s_{n}snEachintegerisisassociatedwithaweightbythefollowingrules:(1)Ifisisnegative,thenitsweightis00.(2)Ifisisgreaterthanorequalto10......
  • 详解Oracle用户解锁命令的两则实现方法
    在安装完Oracle10g之后，想打开sql*plus来学习，然后按照书上的步骤用scott用户来连接数据库，可输了好几次都提示一个错误。error：theaccountislocked然后上网查了一下之后发现这个用户被锁定了，至于它为什么被锁定，可能是下面几个原因。1.尝试多次登录未成功.(可能密码不正确)2.此用......
  • Docker网络详解
    文章目录一、理解docker0网桥二、Docker网络模式三、Docker容器互联四、自定义网络一、理解docker0网桥安装docker的时候，会生成一个docker0的虚拟网桥。每运行一个docker容器都会生成一个veth设备对，这个veth一个接口在容器里，一个接口在物理机上安装网桥管理工具：yuminstallbridg......
  • Docker资源配额详解
    文章目录一、针对CPU限制二、针对内存限制三、针对磁盘限制四、stress压测工具Docker通过cgroup来控制容器使用的资源限制，可以对docker限制的资源包括CPU、内存、磁盘一、针对CPU限制Docker容器针对CPU限制包括--cpu-shares、--cpuset-cpus参数。–cpu-shares：CPU使用份额控制......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99