APTX

A Moe Blog Set By APTX

#C/C++#树状数组模板

问题模型

现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。

这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间复杂度,而查询的话是O(n)的复杂度,总体时间复杂度为O(qn)

可能你会想到前缀和来优化这个查询,我们也来分析下,查询的话是O(1)的复杂度,而修改的时候修改一个点,那么在之后的所有前缀和都要更新,所以修改的时间复杂度是O(n),总体时间复杂度还是O(qn)。

可以发现,两种做法中,要么查询是O(1),修改是O(n);要么修改是O(1),查询是O(n)。那么就有没有一种做法可以综合一下这两种朴素做法,然后整体时间复杂度可以降一个数量级呢?有的,对,就是树状数组。

lowbit函数

lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1

树状数组

这是树状数组的模型

《#C/C++#树状数组模板》

可以看出

通过lowbit函数来得出k,其中k就是该值从末尾开始0的个数。然后将其得出的结果加上x自身就可以得出当前节点的父亲节点的位置或者是x减去其结果就可以得出上一个父亲节点的位置。

所以他就变成logn的数据结构了

模板

树状数组 1

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3个整数,表示一个操作,具体如下:

操作1: 格式:1 x k 含义:将第x个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

输出样例#1:

代码

树状数组 2

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x 含义:输出第x个数的值

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

输出样例#1:

代码

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注