当前位置： 首页 > article >正文

数据结构-树状数组专题（1）

article 2024/11/24 23:37:00

一、前言

树状数组可以解决部分区间修改和区间查询的问题，相比于线段树，代码更加简单易懂

二、我的模板

搬运jiangly鸽鸽的模板，特别注意这个模板中所有涉及区间的都是左闭右开区间，且vector的有效下标都从0开始

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

三、树状数组简介

在单点修改和区间查询（单点查询）中，暴力的算法时间复杂度会非常的高，如果想使用前缀和减少时间复杂度，但是我们发现由于频繁地单点修改，导致无法高效地维护前缀和数组，因此衍生出了我们的这个树状数组的高级数据结构。如下图：

9b76f19ee2314eb191f76afe574c1ce7.png

观察图，易发现：
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

于是我们引入lowbit的概念，就是一个数的二进制表示的最低位1表示的数值，例如6的二进制为110,因此10转换成十进制的值即为2，所以6的lowbit是2

关于计算lowbit，有很多方法，可以通过循环找按位右移去找，也可以用x-(x&(x-1))来计算lowbit，还可以用x&(-x)来计算lowbit（最常用也最简洁），至于原理则跟二进制有关，感兴趣的可以自行去了解

树状数组的性质

单点更新操作

如果要更新某个点，那么从这个点开始，下标一直加上当前的lowbit，直到大于最大长度n结束，都需要同时更新它们的值

查询前缀和

如果要查询前k个数的前缀和，那么前缀和的值就等于从k开始一直减去当前lowbit直到k等于0（k取不到0）结束的所有树状数组的值之和

实现区间查询

只需要实现两个前缀和的查询然后相减即可

假如要查询[l,r]这个区间，那么要求出pre[r]的值和pre[l-1]的值，pre表示前缀和

其中单点查询是区间查询的子情况，只不过此时的l等于r而已

后续的专题（2）还有区间修改+单点查询和区间修改+区间查询的高级应用（结合差分）

具体树状数组的细节可以自行翻阅资料，这里就不再展开讲

四、专题训练

4.1 星码StarryCoding P40 【模板】树状数组（单点修改）

6fc9b892827f42c8a32fb3d477a6db05.png

思路

树状数组的初始化操作实际上也是一个单点修改的操作，这是个模板题，没什么好说的，直接看代码吧

我的代码

注意可能爆int，因此要开long long，还有要注意下标！！！

//Code Here.
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;

template <typename T>
struct Fenwick {
   int n;
   std::vector<T> a;

   Fenwick(int n_ = 0) {
       init(n_);
   }

   void init(int n_) {
       n = n_;
       a.assign(n, T{});
   }

   void add(int x, const T &v) {
       for (int i = x + 1; i <= n; i += i & -i) {
           a[i - 1] = a[i - 1] + v;
       }
   }

   T sum(int x) {
       T ans{};
       for (int i = x; i > 0; i -= i & -i) {
           ans = ans + a[i - 1];
       }
       return ans;
   }

   T rangeSum(int l, int r) {
       return sum(r) - sum(l);
   }

   int select(const T &k) {
       int x = 0;
       T cur{};
       for (int i = 1 << std::__lg(n); i; i /= 2) {
           if (x + i <= n && cur + a[x + i - 1] <= k) {
               x += i;
               cur = cur + a[x - 1];
           }
       }
       return x;
   }
};

int main() {
   std::cin.tie(nullptr)->sync_with_stdio(false);

   int n,q;
   std::cin >> n >> q;
   std::vector<i64> a(N,0);
   for(int i = 1;i <= n;++i) {
       std::cin >> a[i];
   }
   Fenwick<i64> fenwick(N);
   for(int i = 1;i <= n;++i) {
       fenwick.add(i-1,a[i]);
   }
   while(q--) {
       int op,l,r,k,v;
       std::cin >> op;
       if(op==1) {
           std::cin >> k >> v;
           fenwick.add(k-1,v);
       }else {
           std::cin >> l >> r;
           std::cout << fenwick.sum(r)-fenwick.sum(l-1) << '\n';
       }
   }
   
   return 0;
}

4.2 星码StarryCoding P31 求逆序对个数

ae90638a05374c44b0f16acb6b166a52.png

思路

提示很明显了，用归并排序或者树状数组都能写，用树状数组写的时候要注意，由于1<=ai<=1e9，因此不能直接开树状数组，会爆栈，所以需要先对a数组做离散化，再开一个树状数组，数组大小为离散化后的数组大小，数组存放的内容是当前下标对应的离散化数组中的值出现的次数（听着有一点绕，可以看下面的代码辅助理解），然后i从1到n遍历，找当前比a[i]大的值（当前比a[i]大的值全都存储在当前树状数组下标的后面，因此可以用区间查询直接算）有多少个，答案就加上多少，然后修改当前的值加一，最后累加得到的答案输出即可

我的代码1

树状数组实现

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n,q;
    std::cin >> n;
    std::vector<int> a(N,0),v;//v是离散化数组
    for(int i = 1;i<=n;++i) {
        std::cin >> a[i];
        v.emplace_back(a[i]);
    }

    v.emplace_back(0);//放一个0是为了排序后的有效下标从1开始
    //排序去重
    std::sort(v.begin(),v.end());
    v.erase(std::unique(v.begin(),v.end()),v.end());

    Fenwick<int> fenwick(N);
    i64 ans = 0;
    for(int i = 1;i<=n;++i) {
        int idx = std::lower_bound(v.begin(),v.end(),a[i])-v.begin();
        ans+=fenwick.sum(v.size()-1)-fenwick.sum(idx);
        fenwick.add(idx-1,1);
    }
    std::cout << ans << '\n';

    return 0;
}

我的代码2

归并排序实现

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;

i64 ans = 0;
std::vector<int> v(N,0);
std::vector<int> tmp(N,0);

using MERGE_SORT = std::function<void(std::vector<int> &,int,int)>;
MERGE_SORT mergeSort = [](std::vector<int> &v,int l,int r)->void {
    if(l>=r) return;
    int mid = l+r>>1;
    mergeSort(v,l,mid);
    mergeSort(v,mid+1,r);
    int k = 0,i = l,j = mid+1;
    while(i<=mid&&j<=r) {
        if(v[i]<=v[j]) tmp[k++] = v[i++];
        else tmp[k++] = v[j++],ans+=mid-i+1;
    }
    while(i<=mid) tmp[k++] = v[i++];
    while(j<=r) tmp[k++] = v[j++];
    for(int i = l,j = 0;i<=r;i++,j++) v[i] = tmp[j];
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    
    for(int i = 1;i<=n;i++) {
        std::cin >> v[i];
    }
    
    mergeSort(v,1,n);
    std::cout << ans << '\n';
    
    return 0;
}

五、后记

难点在后面与差分结合的区间修改，不过很多人不去学这块，毕竟线段树可以很简单地实现（思维上简单，代码量确实不简单，写着写着就Segment Fault了，不然怎么叫Segment Tree呢[/滑稽]）

 


http://www.kler.cn/a/407832.html

相关文章：

  • mayo介绍和QTqmake编译基于Opencascade开发的mayo工程-小白配置
  • MySQL系列之身份鉴别（安全）
  • 软件测试面试之常规问题
  • React (三)
  • 递归-迭代
  • 【电源专题】BUCK电源SW电压的平均值为什么等于输出电压？
  • uniapp vue2项目迁移vue3项目
  • 【GoogleChrome】在开发者工具中修改js、css并生效
  • 面向对象高级（3）类中属性赋值与final关键字
  • 【2024 Optimal Control 16-745】Ubuntu22.04 安装Julia
  • Java基于SpringBoot+Vue实现酒店客房管理系统（含源码+数据库）
  • 中序表达式转后序表达式
  • 网络安全设备
  • 采用python3.12 +django5.1 结合 RabbitMQ 和发送邮件功能,实现一个简单的告警系统 前后端分离 vue-element
  • Java-05 深入浅出 MyBatis - 配置深入 动态 SQL 参数、循环、片段
  • 分布式 Data Warebase - 构筑 AI 时代数据基石
  • go-zero(八) 中间件的使用
  • 【人工智能】深入理解 Keras：从0开始完整教程！掌握深度学习的核心技术
  • 数据结构 （4）线性表的顺序存储
  • EMD-KPCA-Transformer多变量回归预测！分解+降维+预测！多重创新！直接写核心！
  • 手写一个深拷贝工具
  • 【Java知识】Java进阶-web应用热部署
  • 部署端侧大模型
  • 设计模式学习[9]---模板方法模式
  • 深度学习：GPT-1的MindSpore实践
  • git如何将当前的修改提交到其它分支