粗暴柜子

文章
9
资源
0
加入时间
2年10月17天

Rikka with Ants

链接:https://www.nowcoder.com/acm/contest/148/H来源:牛客网 题目描述There are two small ants on Rikka's desk. If we consider Rikka's desk as a two-dimensional Cartesian coordinate system, both of them have ...

树状数组及其应用 1.普通数组:2.前缀和数组:综上我们发现,两种方法,要么修改极快,查询极慢,要么修改极慢,查询极快 为什么会这样呢?因为我们用的两种数据结构不够优秀。因此我们便引入树状数组来均衡两种数组的特性。首先要知道什么是树状数组: 1.单点修改:2.区间求和3.区间修改和单点查询4.区间求和和区间查询:如果看懂了,希望点个赞支持一下 !

当我们需要用到数组来存放数据并对数据进行操作时,往往有这么几种数组形式:1.普通数组:修改操作:令 a[x]+=k ,时间复杂度O(1)询问操作:输出a[x]+a[x+1]+a[x+2]+…+a[y-1]+a[y] ,时间复杂度O(n)2.前缀和数组:查询操作:直接输出a[y] - a[x-1]就好了,时间复杂度O(1)修改操作:对于所有大于等于x的y,都要让a[y]+=k,时间复杂度O(n);综上我们发现,两种方法,要么修改极快,查询极慢,要么修改极慢,查询极..