代码编织梦想

前缀和

前缀和数组:
初始化:O(n)时间复杂度,顺序扫描原数组即可
查询区间和:O(1)时间复杂度,S[j]-S[i]即为原数组i到j的区间和
单点修改:O(n)时间复杂度,需要修改S[i]~S[n]的所有值

慢,是因为S[i]的值与之前原数组中所有项都有关系
弱化这种关系,即可加快单点修改速度,当然也会丧失部分查询速度,但是这种取舍是值得的。

lowbit函数
定义:lowbit(i)代表i这个数字,二进制表示的最后一位1的位权。
lowbit(x) = x & (-x)

树状数组

改进前缀和:
lowbit(i):代表C[i]代表前lowbit(i)项的和(向前数lowbit项的和)
例如:
lowbit(10) = 2 , C[10] = a[10] + a[9]
lowbit(12) = 4 , C[12] = a[12] + a[11] + a[10] + a[9]
在这里插入图片描述

树状数组的基础知识

基本操作:

前缀和查询:
S[i] = S[i-lowbit(i)] + C[i]
例如:
S[7] = S[6] + C[7] = S[4] + C[6] + C[7] = C[4] + C[6] + C[7]
S[12] = S[8] + C[12] = C[8] + C[12]
单点修改:
当修改A[j]位置的值的时候,首先需要更新的显然是C[j]的值,可C[j]之后,应该更新哪个值呢?也就是找到C[j]脑袋上面的区间。
例如:
更新原数组A[5]的值,那么需要更新C[5],C[6],C[8]的值。
在这里插入图片描述
Leetcode-1109 例题解析:
在这里插入图片描述

//将树状数组建立在查分数组之上
#define lowbit(x) (x & (-x))
class FenwickTree{
public:
    FenwickTree(int size):n(size),c(n+1){}
    void add(int i,int x){
         while(i<=n)c[i]+=x,i+=lowbit(i);
         return;
    }
    int at(int ind){return query(ind)-query(ind-1);}
    int query(int x){
        int sum = 0;
        while(x) sum+=c[x],x-=lowbit(x);
        return sum;
    }
    void output(){
        int len = 0;
        for(int i=1;i<=n;i++){
            len += printf("%5d",i);
        }
        printf("\n");
        for(int i=0;i<len+6;i++){
            printf("=");
        }
        printf("\n");
        for(int i=1;i<=n;i++){
            printf("%5d",c[i]);
        }
        printf("\n");
        for(int i=1;i<=n;i++){
            printf("%5d",query(i)-query(i-1));
        }
        printf("\n\n\n");
        return ;
    }
private:
    int n;//下标上限
    vector<int> c;
};

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        FenwickTree tree(n);
        for(auto x:bookings){
            //x[0] -- x[1]+x[2]
            tree.add(x[0],x[2]);
            tree.add(x[1]+1,-x[2]);
        }
        vector<int> ret(n);
        for(int i=1;i<=n;i++){
            ret[i-1] = tree.query(i);
        }
        return ret;
    }

};
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46571036/article/details/121543655

《算法与数据结构》学习笔记:树状数组_liweiwei1419的博客-爱代码爱编程

14. 《算法与数据结构》学习笔记:树状数组 文章目录 14. 《算法与数据结构》学习笔记:树状数组一、树状数组能解决的问题1、 数组前缀和的查询2、单点更新 二、树状数组长什么样子三、理解数组 C 的定义四

树状数组--快速计算动态前缀和_aamahone的博客-爱代码爱编程

文章目录 问题 && 结论原理实现进阶操作 问题 && 结论 树状数组是一种能够维护动态数组并快速计算动态前缀和的数据结构. 假设有一数组A[n],(A[1]表示数组第一个元

海啸(二维前缀和/二维树状数组)_tb_youth的博客-爱代码爱编程_一i/j:ac -

链接:https://ac.nowcoder.com/acm/problem/21862 来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit I

一个简单的整数问题【树状数组】【维护前缀和】_谁是凶手1703的博客-爱代码爱编程

题目传送门 树状数组可以维护前缀和 区级更新可以差分数组的思想 单点查询 正常查询 #include<iostream> #include<algorithm> using namesp

树状数组-爱代码爱编程

一、树状数组原理 树状数组主要运用于查询任意两点所有元素之和和更改任意一个元素的值 可以看到上图每个节点都管辖了一个范围 eg.节点2管辖了1 ~ 2这个区间,10管辖了9 ~ 10这个区间 那么决定每个节点管辖

树状数组与前缀和差分数组以及二维树状数组-爱代码爱编程

树状数组与前缀和差分数组以及二维树状数组 树状数组基本思想树状数组实现初始化差分数组与前缀和数组成段修改单点查询成段修改成段查询二维树状数组单点修改成段求和成段修改单点查询成段修改成段求和树状数组的其他应用逆序对二维平面排序 树状数组 基本思想 树状数组有称作Binary Index Tree,顾名思义,就是一种以二进制为索引的数据结构。令

「树状数组」第 1 节:树状数组能解决的问题-爱代码爱编程

关键词:位运算、前缀和的查询与更新。 第 1 节 树状数组能解决的问题 树状数组,也称作「二叉索引树」(Binary Indexed Tree)或 Fenwick 树。 它能高效地实现下面两个操作: 数组的「前缀和」查询;数组的「单点更新」。 下面具体解释这两个操作。 数组的「前缀和」查询 首先看下面这个例子,了解什么是数组的前缀和查询。 例

「树状数组」第 3 节:理解 lowbit 操作-爱代码爱编程

下面我们介绍一种很酷的操作,叫做 lowbit ,它可以高效地计算 2 k 2^k 2k,即我们要证明:

算法篇:树状数组-爱代码爱编程

目录 树状数组(二叉索引树)一、前缀和数组1. 数列与其前缀和数列2. 前缀和数组2.1 前缀和数组的计算3. 前缀和数组的用途4. 前缀和数组的复杂度分析4.1 空间复杂度O(n)4.1 时间复杂度4.1.1 创建4.1.2 查询4.1.3 更新5. 前缀和数组适用性二、树状数组1. 产生原因2. 作用3. 优化思路3.1 前缀和与原数组的包含关

【树状数组】树状数组概念与基本使用-爱代码爱编程

做算法题目的时候经常会遇到一些求区间和的内容。比如给你一个数组a[0..100],要你计算哪个区间的元素和为100这类的。 这种题目往常都是采用前缀和数组来解答的。设有数组a[0..100]对应的前缀数组b[0..100],则b元素的值为: 这样我们要求a[m..n]这个区间的内容,原本需要,现在只要计算这样的操作即可。 之所以前缀和数组计算区间和需

重拾树状数组-爱代码爱编程

树状数组 (本文会详细介绍树状数组,萌新也可以轻松看懂) 引言 在做题过程中,我们有时会要维护这样一个前缀和数组: S u m [

树状数组o(n)建树_荼白777的博客-爱代码爱编程

题目来源 以这道题为例子 首先我们知道树状数组是这样的; 图中的C数组就是我们的树状数组; 暴力建树 首先我们可以通过单点修改的方式,暴力建树,但是这种是