乐昌门户网站想建个板栗网站怎么做

乐昌门户网站,想建个板栗网站怎么做,wordpress爱搭配,哪个网站做医学培训好题目链接#xff1a;P3374 【模板】树状数组 1 - 洛谷 注#xff1a;在代码中我不存储原数组值#xff0c;所以按我的习惯树状数组我的数组名叫 arr #xff0c;但是在文字表述中我写得 tr 是表示树状数组的。 我们可能此前就了解过前缀和优化#xff0c;前缀和能够允许…题目链接P3374 【模板】树状数组 1 - 洛谷注在代码中我不存储原数组值所以按我的习惯树状数组我的数组名叫 arr 但是在文字表述中我写得 tr 是表示树状数组的。我们可能此前就了解过前缀和优化前缀和能够允许我们以 O(1) 的时间快速查找。可是一旦我们要频繁修改数组里的值然后再查找前缀和就很慢了因为每次修改都需要重新计算前缀和数组。针对这种情况前缀和已经无法解决我们的需求了。我们需要更厉害的数据结构针对这种维护数组区间和的题目我们能想到的无非就是线段树或者树状数组。线段树我之前的博客已有介绍感兴趣的可以点击链接前去观看有十分详细的图解模拟过程认真看完肯定能理解线段树精髓~线段树详解链接https://blog.csdn.net/h_a_o777oah/article/details/158577964可是线段树虽然十分通用可有个问题就是线段树代码实在不好写。写完代码不仅可能都一百行耗时不说一旦你用得不熟悉写错了Debug 要用的时间和精力可能会让你破防。而且线段树的常数有点大有些时候还是会没这么快。这个时候就要可以用一个十分好用的数据结构树状数组了。树状数组是一种用于高效维护数列前缀和的数据结构。它的核心思想是利用整数的二进制分解将前缀和拆分为若干个不重叠的区间从而实现快速的单点更新和前缀查询。要注意它和线段树还是有点不一样的树状数组是只支持单点修改的而线段树无论区间还是单点都是一样的。lowbit详解及区间查找 ask 过程模拟而谈到树状数组最精华也最让人觉得有点“莫名其妙”的地方就是他的lowbit计算。lowbit的计算公式十分简单其实就是如下代码x-x而已。但其实很奇怪这个东西是怎么能够精准的查到区间的int lowbit(int x) { return x-x; }我先举一个例子看看这个奇妙的树状数组是如何存值的。以数组 [1, 5, 3, 6, 8, 2, 9] 为例按习惯我们以1为下标开始。这么看似乎更奇怪了树状数组里每个值都是表示了什么可以根据下面我给出的表自己查找一下每个值都代表了什么树状数组设为 tr tr[1]维护区间 [1,1] 的值就是原数组第一个数 1 。tr[2]维护区间 [1,2] 的值就是原数组的 15 。tr[3]维护区间 [3,3]的值就是原数组的 3 。tr[4]维护区间 [1,4] 的值就是原数组的 1536 。tr[5]维护区间 [5,5] 的值就是原数组的 8 。tr[6]维护区间 [5,6] 的值就是原数组的 82 。tr[7]维护区间 [7,7] 的值就是原数组的 9 。看上去这些区间的排布好像非常地没有规律没有规律地划分我们怎么查找呢但其实不是树状数组的区间分布规律隐藏很深下面就具体说明。首先我们先了解一下二进制的相关知识。我们都知道任何十进制整数可以被作为二进制表示也就是表示为2的幂次方的和系数为0或1。比如6的二进制表示接下来的二进制都用8位也就是一个字节表示就是 00000110 表达成幂次方的和就是 1 × $2^2$ 1 × $2^1$ 。就是把二进制数的每个 1 位拿出来乘上对应的幂次大小再相加。到了这里我们还要了解计算机中反码和补码的概念。反码和补码是为了在计算机中表达负数而生的。如果是正数的反码就不需要改变二进制数但是负数的反码要先对它正数二进制的每一位按位取反。而补码就是再在反码基础上加 1 。计算机里存储的负数就是补码。第一个位一般是符号位正数为0负数为1。说到这里回到我们的树状数组。里面的区间分布看似是无意义的其实我们回想一下既然每个数都能用二进制表示那就是说我如果要查询区间 [1,n] 那我可以把他利用二进制划分成好几个区间。比如查询区间 [1,6] 我们想想 6 的二进制可以把这个区间拆解成 [1,4] [5,6] 长度分别为 4 和 2 那这个区间长度和正好就是6而且树状数组独特的划分方式如何划分等会再说也给了我们查询的便捷。光说我们是看不出什么的我们可以来演示一下查找过程。看完可能就理解了树状数组的理念了。比如我们要查找区间 [1,6] 拿一个 sum 记录一下树状数组就是只能查到底的全部累加在一起首先进入的当然是树状数组索引为 6 的点了加上之后我们区间 [5,6] 就已经完成查找了。但是还有区间 [1,4] 还要去找。我们来看看6的二进制形式 00000110 我们加完当前的索引值后其实就要让末尾的1去掉表示这个长度的区间我们已经加上了可以加下一个区间长度的了。那现在我们已经完成了区间为 2 的查找就要把那个 1 删掉继续查找 $2^2$ 区间长度。减掉之后我们发现数字变成了 00000100也就是 4 我们去到索引为 4 的地方加去给 sum。现在 00000100 的地方也找完了我们把末尾的1删去变成了 00000000 查找结束我们也找到了从索引1累加的6的值了。经过这次查找我们其实可以发现了树状数组的区间分布是有规律的让我们能够通过二进制的一次次跳跃到末尾的1去查找查找完成删掉末尾的1继续查找直到为0。但是有个问题我们虽然可以遍历一下二进制位数来查找末尾的 1 但我们其实有更优雅的办法就是利用 lowbit 函数代码十分简洁。回忆一下lowbit 函数就是 x-x 而已但-x在计算机中存储的是补码我们回想一下补码的特点它是反码1得来的。反码是原码的按位取反加一之后由于进位的性质只要进行运算就必然能把原码末尾的1的位置给找出来。比如我们看看 6-6是如何计算的。没错这个运算并非什么“神迹”不过是一种更优雅的写法快速找出末尾1的位置而已。我们来看看这个 ask 区间查找函数也许会震惊于它的简洁。long long ask(int x) { long long sum0; for(int ix;i0;i-lowbit(i)) sumarr[i]; return sum; }到现在这个树状数组的“秘密”就能揭开了它实际上的定义是对于树状数组tr[i]即从原数组arr从下标i开始向前面数lowbit(i)个元素的和。单点修改 chag 函数所以对于我们 chag 函数修改要怎么办呢我们只需要按照这个树状数组定义哪一个点我们修改了我们在包含他的区间里修改就行了寻找区间还是利用了进位和找到最后一位1的办法一步一步演示如何进行修改。比如我们将第3个数加上4。首先当然修改索引为3的地方我们直接加上4。下一步我们计算出 lowbit(3)答案很明显是 1。我们在3基础上加上1看看。没错我们来到了索引为4的地方这里存储的是区间 [1,4]的区间值正是包含了索引 3 的地方我们修改这个地方的值后再计算 lowbit(4)4 加上去看看。索引到了8但我们并没有8这个索引维护的区间我们修改完了可以return。单点修改完成我们可以回去看看我们所有包括原数组索引为3的值都修改好了吗我们确实已经全部修改好了利用这个 lowbit 计算我们很简单就达成目的。原因也很简单我们树状数组每个索引只维护前面自身 lowbit 长度的区间值。在这次模拟中我们很容易发现每次加上 lowbit 进位后那个索引数字的最末尾1的位置转化成十进制数必然是比我们要修改的索引大的。也就是说每次加上 lowbit 我们都能完美地必然找到包含这个修改索引值的区间比如我们修改的位置是 3 而我们最终修改了树状数组 34位置到 8 不存在结束。我们看看 4 这个数二进制为 00000100 这个最末尾的 1 单独拎出来转化为十进制其实就是 4 。也就是证明了每次加上自身 lowbit 找到的必然是包含这个要修改索引 3 的值的。讲的比较笼统其实自己多模拟几次修改不难发现这个性质和原因知道了基本原理这个 chag 函数比 ask 更加简洁。void chag(int x,long long k) { for(int ix;in;ilowbit(i)) arr[i]k; }p3374 模板代码到这里对于树状数组也许会有一个清晰的认识了。我们来看看这个题目 p3374 模板代码。#include bits/stdc.h using namespace std; int n,m; long long arr[500010]; int lowbit(int x) { return x-x; } void chag(int x,long long k) { for(int ix;in;ilowbit(i)) arr[i]k; } long long ask(int x) { long long sum0; for(int ix;i0;i-lowbit(i)) sumarr[i]; return sum; } int main() { cinnm; for(int i1;in;i) { int t; cint; chag(i,t); } for(int i1;im;i) { int op; cinop; if(op1) { int x; long long k; cinxk; chag(x,k); }else { int x,y; cinxy; coutask(y)-ask(x-1)\n; } } }没错代码十分简洁优雅。线段树要想写完可是非常吃力的而树状数组短短几行就能完成了代码注意事项树状数组一开始一般都是默认里面的值全是零如果有输入我们用 chag 函数往里面加值。这样是比较标准简单的做法。而且要注意树状数组的 ask 函数查找的是前缀和而不是某个点的值最终其实我们还是要用前缀和的做法来得到区间和即 ask(y)-ask(x-1) 。而且虽说树状数组简单但其实泛用性还是没有线段树这么强。因为树状数组它的 ask 是像拼积木一样一个一个把数据拼起来否则就无法利用这个树状数组性质得到想要的答案。而且目前我们这个树状数组只能支持单点修改还有区间查询相比于线段树还是有点不尽人意的但我们还有别的办法让他能够支持区间修改或者单点查询。这个就以后再说了~另外暂时理解不了也没关系因为我感觉这个树状数组的存储本身是利用了二进制的性质而用惯了十进制的人类思维转换其实是很难适应的。所以第一次看不懂也没关系只要懂了 lowbit 自己在纸上推演几次计算几次二进制的运算也许会有更好更深刻的理解。