首页 > 其他分享 >刍议树状数组

刍议树状数组

时间:2024-08-07 18:07:18浏览次数:14  
标签:树状 int sum 刍议 add 数组 ask

树状数组

用处

区间加,单点查询
单点加,区间查询
区间加,区间查询
求逆序对
……

思想

树状数组的思想对于线段树等结构来说比较抽象,所以我也懒得讲……
在这我只讲一下我对于树组的理解,对于实战来说完全够用。

先讲一个叫 \(lowbit\) 的东西,求一个数二进制下最后一个 \(1\) 的位置,比如 \((1010110)_2\) 的 \(lowbit\) 为 \((10)_2\) 。

然后在树状数组里我们定义一个 \(c\) 数组,里面存区间 \([i-lowbit(i)+1,i]\) 的所有数之和。

然后你可以这样理解: 对于二进制 \(i\) 位上的为 \(1\) ,查询的时候累计所有第 \(i\) 位置上为 \(1\) 的 \(c_i\) 之和,修改的时候把每一个二进制上的为 \(1\) 的位置来修改。

有些抽象,还是看代码吧……

树状数组支持的操作有两种

\(1.\) 查询前缀和

int ask(int x){
    int ans=0;
    while(x<=n){
        ans+=c[x];
        x+=lowbit(x);
    }
    return ans;
}

$ 2. $ 单点修改

int add(x,k){
    while(x){
        c[x]+=k;
        x-=lowbit(x);
    }
} 

求逆序对

用 \(t[val]\) 来记录每个数在数组 \(a\) 出现的次数,我们再用树状数组来维护这个前缀和。

逆序对条件 $i<j $ 并且 \(a[i] > a[j]\)

So 从右往左遍历数组 \(a\)
步骤:
\(1.\) 查询当前 t[a[i]-1] 的前缀和,累加到答案上,因为是从右往左扫的,所以比当前位置的数小的就是逆序对的个数,自己好好想一想是不是这样。

$ 2. $ 单点增加,把 \(a[i]\) 的出现次数+1,即 \(t[a[i]]\)++ ,同时维护其前缀和。

代码

for(int i=n;i;i--){
    ans+=ask(a[i]-1);
    add(a[i],1);
}

复杂度为 \(O( (N+M) log M )\),$ M $为数据范围大小

当然了,当数据范围较大时,要先离散化,本生就要排序,所以在数据范围较大时不如直接用归并排序。

例题:

https://www.acwing.com/problem/content/description/243/

区间修改,单点查询

用差分思想,树状数组维护一个差分数组数组 \(b\)

操作时

add(l,d);
add(r+1,-d);

就行了。

例题:

https://www.luogu.com.cn/problem/P3368

区间修改,区间查询

修改操作思路不变,用差分数组 \(b\) 来实现。

emm……下面太难写了,拉一段李煜东大哥的书吧


在本题中,我们增加一个树状数组,用于维护 \(i*b[i]\) 的前缀和,然后可以直接进行查询、计算。
具体来说,我们建立两个树状数组 \(c0\) 和 \(c1\) ,起初全部赋值为零。对于每条指令 \(“C l r d”\),执行4个操作:

然后……
步骤:
1.在树状数组 \(c0\) 中,把位置 \(l\) 上的数加 \(d\)。
2.在树状数组 \(c0\) 中,把位置 \(r+1\) 上的数减 \(d\)。
3.在树状数组 \(c1\) 中,把位置 \(l\) 上的数加\(l* d\)。
4.在树状数组 \(c1\) 中,把位置 \(r+1\) 上的数减 \((r+1)*d\) 。

另外,我们建立数组 \(sum\) 存储序列 \(a\) 的原始前缀和。对于每条指令 \(“Qlr”\) 当然还是拆成 \(1~r\) 和 \(1~l-1\) 两个部分,二者相减。写成式子就是

sum[r]+(r+1)*ask(0,r)-ask(1,r) -  
sum[l-1]+l*ask(0,l-1)-ask(1,l-1);

例题:
https://www.acwing.com/problem/content/description/244/

大家应该不会偷懒去写线段树吧……

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N=1e5+5;
int a[N],sum[N],c[2][N];//c[0]->b[i]c[1]->i*b[i]
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
int lowbit(int x){
    return x&-x;
}
void add(int x,int id,int k){
    while(x<=n){
        c[id][x]+=k;
        x+=lowbit(x);
    }
}
int ask(int id,int x){
    int ans=0;
    while(x){
        ans+=c[id][x];
        x-=lowbit(x);
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    FOR(i,1,n){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    while(m--){
        char opt;
        int l,r,d;
        cin>>opt>>l>>r;
        if(opt=='C'){
            cin>>d;
            add(l,0,d);
            add(r+1,0,-d);
            add(l,1,l*d);
            add(r+1,1,-(r+1)*d);
        }
        else{
            int ans=sum[r]+(r+1)*ask(0,r)-ask(1,r);
            ans-=sum[l-1]+l*ask(0,l-1)-ask(1,l-1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

作业:
https://www.acwing.com/problem/content/description/245/
作业提示:二分答案……

完结撒花

喜欢的点个赞,感激不尽

标签:树状,int,sum,刍议,add,数组,ask
From: https://www.cnblogs.com/yingxilin/p/18347365

相关文章

  • Kotlin 控制流和数组操作详解
    Kotlinwhen与编写许多if..else表达式相比,您可以使用when表达式,它更易读。它用于选择要执行的多个代码块中的一个:示例使用星期几的编号来计算星期几的名称:valday=4valresult=when(day){1->"Monday"2->"Tuesday"3->"Wednesday"4->"Thursday......
  • leetcode 1486. 数组异或操作 https://leetcode.cn/problems/xor-operation-in-an-arr
    1486.数组异或操作题目描述给你两个整数,n和start。数组nums定义为:nums[i]=start+2*i(下标从0开始)且n==nums.length。请返回nums中所有元素按位异或(XOR)后得到的结果。示例示例1:输入:n=5,start=0输出:8解释:数组nums为[0,2,4,6,8],其中(0^......
  • 代码随想录算法训练营day06|242.有效的字母异位词,349.两个数组的交集,202.快乐数,1.两数
    242.有效的字母异位词题目链接:https://leetcode.cn/problems/valid-anagram/description/我的代码:classSolution{public:boolisAnagram(strings,stringt){if(s.size()==t.size()){intrecord[26]={0};for(inti=0;i......
  • 一维数组
    一维数组特点一维性:数组中的所有元素都排列在一条直线上,只有一个维度。类型一致性:数组中的所有元素都必须是相同的数据类型。索引访问:通过索引可以快速访问数组中的任何元素。索引通常从0开始,但这也取决于编程语言的约定。固定大小(或动态大小):在静态类型语言中,数组的大小在创......
  • 数组的算法
    数组的算法目录数组的算法1.数组排序2.数组查找3.数组求和、求最大值和最小值4.数组反转5.数组乱序6.数组复制7.数组去重1.数组排序冒泡排序:通过重复遍历要排序的数组,比较相邻元素的大小,并在必要时交换它们的位置,直到整个数组排序完成。冒泡排序的时间复杂度为O(n^2)......
  • 一维数组
    4.1一维数组目录4.1一维数组4.1.1认识数组数组的定义4.1.2数组的创建及初始化4.1.3遍历数组for循环遍历foreach遍历4.1.4数组作为传参,调用该方法时,是否改变原数组?4.1.5Arrays类4.1.1认识数组数组的定义文字定义:数组是一种数据结构,用于存储多个相同类型的数据。Java......
  • JavaScript 数组方法
    JavaScript数组的力量隐藏在数组方法中。把数组转换为字符串JavaScript方法toString()把数组转换为数组值(逗号分隔)的字符串。join()方法也可将所有数组元素结合为一个字符串。它的行为类似toString(),但是您还可以规定分隔符<pid="demo"></p><script>varfruits......
  • 请遍历一个数组 , 输出数组的各个元素值。
    1publicclassshuzu21{2//编写一个main方法3publicstaticvoidmain(String[]args){45//编写一个数组,输出数组的各个元素值6int[][]map={{0,0,1},{1,1,1},{1,1,3}};7//使用方法完成输出,创建MyTools对象89......
  • Cython将Numpy数组转为自定义结构体
    技术背景前面我们写过几篇关于Cython的文章,例如Cython计算谐振势、Cython与C语言的结合、Cython调用CUDAKernel函数。Cython有着非常Pythonic的编程范式,又具备着接近于C语言的性能,因此在很多对于性能有要求的Python软件中都会使用到Cython的性能优化。Cython的基本工作流程是,先......
  • Java中对数组的学习
    数组的概念目录数组的概念声明数组变量创建数组处理数组数组作为函数的参数数组作为函数的返回值数组对于每一门编程语言来说都是重要的数据结构之一,当然不同语言对数组的实现及处理也不尽相同。Java语言中提供的数组是用来存储固定大小的同类型元素。你可以声明一个数组变......