树状数组，谁发明了树状数组

本文目录一览

1，谁发明了树状数组
2，神犇求解树状数组能求区间最值吗时间复杂度是多少啊还有就
3，树状数组怎么储存数据
4，树状数组解决最长不下降子序列讲讲主要思路就好

1，谁发明了树状数组

Peter Fenwick

你好！sdadas希望对你有所帮助，望采纳。

谁发明了树状数组

2，神犇求解树状数组能求区间最值吗时间复杂度是多少啊还有就

树状数组是用来算静态序列区间子段和的，不能用来求最值，静态序列求区间最值得话应该用Rmq，与此相关的算法还有线段树（这个前面说的都能求，而且可以动态维护）。

神犇求解树状数组能求区间最值吗时间复杂度是多少啊还有就

3，树状数组怎么储存数据

(1)树状数组中的每个元素是原数组中一个或者多个连续元素的和。　　　　(2)在进行连续求和操作a[1]+...+a[n]时，只需要将树状数组中某几个元素的和即可。时间复杂度为O(lgn)　　　　(3)在进行修改某个元素a[i]时，只需要修改树状数组中某几个元素的和即可。时间复杂度为O(lgn)

树状数组怎么储存数据

4，树状数组解决最长不下降子序列讲讲主要思路就好

不降子序列求的是一个元素的值单调不降的序列。传统的状态设计便是使用f[n] 表示到达第n位时的最长不降子序列。那么转移就是f[n]=max(f[i]+1)其中要求a[i]<=a[n] && i<=n那么想要使得复杂度比较优，就不能通过枚举所有满足条件的i来找到最优解。那么树状数组在其中能起到什么作用呢？可以起到很快的查询到最优的f[i]的作用。这里的树状数组是当做桶来使用的。我们可以先考虑桶的情况。我们现在开一个桶，其下标 x 表示 a[i]=x 的f[i]的最大值。T[x]=max(f[i]); //其中a[i]=x那么需要转移到f[n]的话，就先找到a[n]在桶中的位置，然后查询所有a[n]之前所存储的最大值中的最大值。也就相当于是一段前缀中的最大值。f[n]=max(T[x]+1); //其中x<=a[n]在枚举f[n]的同时，也将f[n]的值扔入桶中，方便之后的更新。T[a[n]]=max(T[a[n]],f[n]);而桶的前缀和是可以用树状数组来优化的，那么查询一段前缀的最大值和更改某个位置的值就可以在log(W)的时间内完成了。void Modify(int x,int d) for(;x<=SIZE;x+=x&-x) T[x]=max(T[x],d);}int Find_Max(int x) int Max=0; for(;x;x-=x&-x) Max=max(Max,T[x]); return Max;}for(int i=1;i<=n;i++) f[i]=Find_Max(a[i])+1; Modify(a[i],f[i]);}特别注意的就是n和SIZE的区别，其中SIZE表示的是最大的a[i]值，因为我们是用a[i]来作为下标储存的。再啰嗦一下就是当a[i]的范围不是10^6以下，但是n是10^6以下的时候，仍然是可以做的，那么就需要对a[i]进行离散化操作了。