先把 lowbit 写出来
补全 lowbit:取出 x 二进制里最低那个 1 代表的值。 算 lowbit(12)。
建树状数组并查前缀和
补全 fen_prefix:从下标 i 出发一路减 lowbit,把沿途的值加起来。 查前 3 个数的和。
任意一段区间的和
补全 fen_range:用两次前缀和相减求出区间 [l, r] 的和(下标从 1 开始)。 求第 2 到第 4 个的和。
改一个值,前缀和跟着变
补全 fen_add:给第 i 个元素加上 v,沿途一路加 lowbit 往上更新。 给第 2 个加 10,然后重新查前 3 个的和。
它说"在"意味着什么
布隆过滤器返回"在"的时候,实际含义是【0】。
它说"不在"意味着什么
布隆过滤器返回"不在"的时候,实际含义是【0】。
能不能从布隆过滤器里删元素
标准的布隆过滤器【0】。
查一个真的加过的
8 位的布隆过滤器,两个哈希函数:k % 8 和 (k * 3) % 8。已经加进了 17、24、15。运行下面这段程序: def h1(k): return k % 8 def h2(k): return (k * 3)
查一个从没加过的
同一个过滤器。运行下面这段程序: def h1(k): return k % 8 def h2(k): return (k * 3) % 8 def add(bits, k): bits[h1(k)] = 1
写 add:把两位都置上
补全 add:把 k 的两个哈希位都置成 1。 加完 17、24、15 之后,输出一共有几位被置上了。