锐客网

  1. 首页 > it技术 > >

A|关于树状数组的几点总结

本文不一定适合初学者
零、树状数组的基本概念 1.概念：
  • 树状数组是一种支持对数列进行快速的区间操作（如：区间编号为1~10的值统一增加某个数）的数据结构。
【A|关于树状数组的几点总结】2.实现原理：
  • 二进制加法
  • 位运算
  • 补码和原码
  • （第一个决定了这个数据结构的理论有效性，第二和第三个决定了具体实现）
3.特性：
  • 如果观察树状数组的结构，可以发现：树状数组的结构就像是一个去掉右结点的线段树的结构.（这决定了树状数组的空间复杂度为A|关于树状数组的几点总结
    文章图片
  • 代码量很少，最基本的树状数组（单点修改区间查询）的有效代码可能还不到十行.
一、单点修改区间查询 1.概念：
  • 这是树状数组最基本的应用，也就是支持单点修改区间查询（时间复杂度均为A|关于树状数组的几点总结
    文章图片
    ）
2.实现原理：
  • 图片：
A|关于树状数组的几点总结
文章图片

3.具体实现（这里只写大概的运行过程）：
  • A|关于树状数组的几点总结
    文章图片
    数组的用途：用于保存原数列各元素的值.
  • A|关于树状数组的几点总结
    文章图片
    数组的用途（假设一个C数组的下标i）：用于保存 在i的二进制表示中，最后一位1后面的0的数量的，从i开始往左走这个数量步，经过的a数组中的每一个值，的和.（如果写的不清楚可以看图）
  • 实现原理：二进制刚好满足这个条件.（结合下标观察+自己手写即可理解）
  • 单点修改（假设要给序列中序号为i的地方的值增加x）：
  1. 不停获取i的二进制表示中的最后一位1所代表的值（将这个值设为b）
  2. 在操作过程中（在循环中给i增加b之前），向C数组中下标为i的地方增加x
  3. 进行i+b这个操作（这使得i的值在最坏情况下也会在A|关于树状数组的几点总结
    文章图片
    次达到A|关于树状数组的几点总结
    文章图片
    （估算））
  4. 判断i的值是否到n
  • 区间查询：
  1. 准备进行两次求前缀和的操作（假设要获取区间a[i...j]的总值，则计算A|关于树状数组的几点总结
    文章图片
    即可，也就是求两次前缀和）
  2. （单次求前缀和操作过程与单点查询恰好相反）（下面只写求单次前缀和的过程，具体可看代码.）
  3. 初始化ans=0，准备用于存储查询结果
  4. 不停获取i的二进制表示中的最后一位1所代表的值（将这个值设为b）
  5. 在操作过程中（在循环中给i减少b之前），向ans增加x
  6. 进行A|关于树状数组的几点总结
    文章图片
    这个操作（这使得i的值在最坏情况下也会在A|关于树状数组的几点总结
    文章图片
    次达到A|关于树状数组的几点总结
    文章图片
    （估算））
  7. 判断i的值是否到0
  • 一句话总结：修改时改比自己大的，改到头；查询时利用前缀和的思想算差值即可.
题目地址：https://www.luogu.org/problemnew/show/P3374
#include #include using namespace std; int n,c[500010]; int lowbit(int x){ return x&-x; } void add(int x,int k){ for(; x<=n; x+=lowbit(x))c[x]+=k; } int sum(int x,int y){ int ans=0; for(; y; y-=lowbit(y)){ ans+=c[y]; } for(x--; x; x-=lowbit(x)){ ans-=c[x]; } return ans; } int main(){ int m; scanf("%d%d",&n,&m); for(int i=1; i<=n; i++){ int k; scanf("%d",&k); add(i,k); } for(int i=1; i<=m; i++){ int ta,tb,tc; scanf("%d%d%d",&ta,&tb,&tc); if(ta==1){ add(tb,tc); }else if(ta==2){ cout<

二、区间修改单点查询 1.概念：
  • 使用普通的树状数组维护差分数组，即可实现"区间修改单点查询"的操作.
2.实现原理：
  • b[l...n]+delta,b[r+1...n]-delta <=> a[l...r]+delta.
  • 区间修改：将原有的单点修改改为两次对单点的值修改.
  • 单点查询：对于任意一个数，在树状数组内仅有在它之前的数可能影响它，因此只要(while(x)x-=lowbit(x){ans+=tr[x]}即可.
题目地址： https://www.luogu.org/problemnew/show/P3368
#include #include #define lowbit(x) x&-x using namespace std; long long c[500050]; int n,m; void add(int x,int num){ for(; x<=n; x+=lowbit(x))c[x]+=num; } long long query(int x){ long long ans=0; for(; x; x-=lowbit(x)){ ans+=c[x]; } return ans; } int main(){ scanf("%d%d",&n,&m); int last=0; for(int i=1; i<=n; i++){ int ta; scanf("%d",&ta); add(i,ta-last); last=ta; } for(int i=1; i<=m; i++){ int ta; scanf("%d",&ta); if(ta==1){ int tb,tc,td; scanf("%d%d%d",&tb,&tc,&td); add(tb,td); add(tc+1,-td); }else if(ta==2){ int tb; scanf("%d",&tb); cout<

    推荐阅读


    上一篇：C++|C++ P1090 合并果子

    下一篇：VUE 实现 Table的动态绑定