免费行情软件网站下载大全安全吗,网站是如何盈利的,网络营销方式方法有哪些,网站制作外包是怎么做的大家好#xff0c;我是人见人爱#xff0c;花见花开#xff0c;车见车爆胎的树状数组Peter Pan#xff0c;hhh
讲正文前#xff0c;先来一个长文警告⚠很重要的知识点#xff1a;L SB#xff08;SB#xff1f;#xff09;
LSB 怎么算呢#xff1f; 哦……懂了…大家好我是人见人爱花见花开车见车爆胎的树状数组Peter Panhhh
讲正文前先来一个长文警告⚠很重要的知识点L SBSB
LSB 怎么算呢 哦……懂了代码应该长这样
int lowbit(int n){ return n(-n);}
来既然懂了给大家做一道题吧 答案应该是B啊
二进制索引树树状数组 那么我们如果用我们学过的算法来做的话能得几分呢 基本思想
根据任意正整数关于2的不重复次幂的唯一分解性质若一个正整数x的二进制表示为10101其中等于1的位是024则正整数x可以被“二进制分解”成。进一步地区间[1,x]也可以分成个小区间
①长度为的小区间[1,]
②长度为的小区间[,]
③长度为的小区间[,]。树状数组就是以上的思想。
我们建立一个数组c其中c[x]保存序列A的区间[x-lowbit(x)1,x]中所有数之和。其实c数组可以被化成一个树 这个树的重要性质是“除树根外每个内部节点c[x]的父节点是c[xlowbit(x)]”。
那么我怕你们还是不懂请看下图 先给大家看看查询前缀和的代码吧
int sum(int i){int ans0;while(i){ansc[i];i-lowbit(i);}return ans;
}
有人会问了为什么i要自减lowbit(i)呢因为上一步的c[i]表示[i-lowbit(i)1,i]为了连续下一步结尾要是i-lowbit(i)所以说我们要用i-lowbit(i)衔接。 大家查询懂了那么更新怎么实现呢给数组内A[x]加上一个y主要影响的是上上上图中c[x]的所有祖先由上上上图的性质知c[x]的父节点是c[xlowbit(x)]也就是说我们要不断地加lowbit(x)下面给出代码
void update(int x,int y){while(xn){c[x]y;xlowbit(x);}
}
那么核心代码讲完了怎么看我干嘛做题啊啊啊啊
最强大脑之八
题目描述
lester参加最强大脑比赛比赛内容是默记对一个序列的操作 序列长度固定为n初始取值均为0 每次操作由3个数描述t,x,y其中 t1表示要求写下序列第x到y个位置上包含x,y的数值之和取模100000007的余数 t2表示序列的第x个位置上的数加上y lester靠心算就能完成这些简单的操作你就不行了所以你只能写代码实现怎么贬低我
