Loading... ## 上午 关键词：树状数组，补码 ### 原码、反码、补码 - 原码：原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值。 - 反码： - 正数的反码是其本身。 - 负数的反码是在其原码的基础上, 符号位不变，其余各个位取反。 - 反码： - 正数的补码是其本身。 - 负数的补码是在其原码的基础上, 符号位不变，其余各个位取反, 最后加一。 关于补码，前面的运算规则是人为规定的，是为了方便记忆。其实他的数学原理是**模**。**模**是指一个计量系统的计数范围。 比如$x\%128$的范围在$[0,128)$之间。因为计算机的数据有大小限制，所以它存在一个**模**。凡是有模的计量器，减法都可以转化为加法。 例如：假设当前时针指向10点，而准确时间是6点，调整时间可有以下两种拨法：一种是倒拨4小时，即：10-4=6；另一种是顺拨8小时：10+8=12+6=6 ，那么在这里，8就是-4的“补码”。 ### 树状数组 ![树状数组结构][1] ![树状数组数据大小][2] #### 单点更新 修改了$a[3]$的值，维护$c$数组。由图知需要修改$c[3] \Rightarrow c[4] \Rightarrow c[8]$。转为二进制来看：$c[(0011)_2] \Rightarrow c[(0100)_2] \Rightarrow c[(1000)_2]$ #### 区间查询 我们总是先求$[1,pos]$的和，然后 用前缀和的思想来求任意区间的和。比如$sum[1,7] = c[7] + c[6] + c[4]$换成2进制来看$sum[1,7] = c[0111_2] + c[0110_2] + c[(0100)_2]$ #### 代码 ```cpp const int N=50000; int c[50002]={0}; int lowbit(int k) { return k&-k; } int add(int f,int num) { for(int i=f;i<=N;i+=lowbit(i)) c[i]+=num; return 0; } int query(int end) { int ans=0; for(int i=end;i>0;i-=lowbit(i)) ans+=c[i]; return ans; } int query(int l,int r) { return query(r)-query(l-1); } ``` ## 下午 切你~~大爷~~。 ## 晚上 晚上发了一张作息时间表。 ![暑假作息表][3] [1]: https://www.oss.starroad.top/usr/uploads/2019/07/2504348382.png [2]: https://www.oss.starroad.top/usr/uploads/2019/07/2535204487.png [3]: https://www.oss.starroad.top/usr/uploads/2019/07/1039758900.jpg<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/346.html">https://www.starroad.top/archives/346.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：July 10th, 2019 at 07:30 pm © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
