上午

关键词：树状数组，补码

原码、反码、补码

• 原码：原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值。

• 反码：

  • 正数的反码是其本身。
  • 负数的反码是在其原码的基础上, 符号位不变，其余各个位取反。

• 反码：

  • 正数的补码是其本身。
  • 负数的补码是在其原码的基础上, 符号位不变，其余各个位取反, 最后加一。

关于补码，前面的运算规则是人为规定的，是为了方便记忆。其实他的数学原理是模。模是指一个计量系统的计数范围。 比如$x\%128$的范围在$[0,128)$之间。因为计算机的数据有大小限制，所以它存在一个模。凡是有模的计量器，减法都可以转化为加法。

例如：假设当前时针指向10点，而准确时间是6点，调整时间可有以下两种拨法：一种是倒拨4小时，即：10-4=6；另一种是顺拨8小时：10+8=12+6=6 ，那么在这里，8就是-4的“补码”。

树状数组

单点更新

修改了$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]$

代码

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);
}

下午

切你大爷。

晚上

晚上发了一张作息时间表。

版权属于：淡淡的路瑶

本文链接：https://www.starroad.top/archives/346.html

如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！