成都外国语学校信息学集训课 Day3

上午

关键词:树状数组,补码

原码、反码、补码

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

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

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

关于补码,前面的运算规则是人为规定的,是为了方便记忆。其实他的数学原理是是指一个计量系统的计数范围。 比如$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);
}

下午

切你大爷

晚上

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

暑假作息表

Last modification:July 10th, 2019 at 07:30 pm
如果您觉得我的文章有用,请赏一颗糖糖。

Leave a Comment