2023.7.26 学习笔记

常规
1

树状数组

树状数组的操作基于 lowbit 运算, 即取二进制最低位的运算

例: lowbit(6) = 2, \ lowbit(32) = 32

  • 原码 : 一个数的二进制表示
  • 反码 : 原码每位翻转
  • 补码 : 反码 + 1

（一般用补码表示负数）

故 lowbit(x) = (x) & (-x)

  • 管辖区间 :

树状数组是一个数组, 数组中的每一个元素都储存了一段数的和, 具体而言， 对 a_n 建立的树状数组 b_n ,

其中第 i 项满足 b_i = \sum ^i _{j = i - lowbit(i) + 1} a_j

  • 查询前缀和 : O(n\log(n)

while(u){
	ans += b[u];
	u-= lowbit(u);
}

  • 单点修改 : O(\log(n))

1 : b_1, b_2, b_4, b_8, ...

2 : b_3, b_4, b_8, ...

以此类推可知 :

while(u <= n){
	b[u] += k;
    u += lowbit(u);
}

注意 i += lowbit(i)

i += lowbit(i) 一定会导致 i 最低位的 1 发生进位.

若 j = i + lowbit(i) 则 i > j - lowbit(j)

这意味着 a_i 包括于 b_j 里面

且 b_j 是 b_i 之上第一个包含 a_i 的节点

  • 区间求和 : O(\log(n))

可转化为两个序列的前缀和 query(l, r) = query(1, r) - query(1, l - 1)

  • 建树 :

O(nlogn) : 逐个插入

O(n):

void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

O(n) : 定义法

void init(){
	for(int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + a[i], b[i] = s[i] - s[i - lowbit(i)];
}

  • 扩展 :

在差分数组上建立树状数组, 即可实现区间修改与单点查询.

  • 优点 : 常数小， 代码短.

eg1 : 求逆序对

​ 权值线段树 / 权值树状数组 (即桶)

a_i 表示 i 出现的个数

假设当前数为 x 则在权值树状数组里查询 x + 1 到 n 的和, 将和累加到答案里, 在下标 x 处插入 1

如此遍历所有元素, 即得答案

(数据范围过大时需离散化)

memcpy(b, a, sizeof n);
sort(b, b + n);
a[i] = lower_bound(a + 1, a + n + 1, x) - a

eg2 : how to use binary search

  • 单点修改
  • 给定 S , 求最小的下标 i, 使得 \sum^i_{j = 1} a_j \ge S

solution :

O(n\log^2(n)) : 二分 i

O(\log(n)) :

  • 转化为求最大的下标 \sum^i_{j = 1} a_j < S

  • 答案为 i + 1

  • 用倍增 LCA 的思想, 按位枚举.

eg3 : P1966 [NOIP2013 提高组] 火柴排队

solution :

\ \ \ \ \ \sum(a_i - b_i)^2 = \sum[(a_i^2 + b_i^2) - 2a_ib_i] = k - 2\sum a_ib_i

可根据排序不等式得 { a_n } , { b_n } 按序排列即可.

求最小交换次数可固定一个数组, 交换另一数组.

eg4 : P1972 [SDOI2009] HH的项链

solution :

  • 把询问按右端点排序

  • 对于若干个区间 [l, r] 如果他们的r都相等的话，那么项链中出现的同一个数字，一定是只关心出现在最右边的那一个的

  • 维护一个树状数组

    看下面的例子：

    1\ 2\ 1\ 3\

    对于第一个 1 , insert(1,1)； 表示第一个位置出现了一个不一样的数字，此时树状数组所表示的每个位置上的数字（不是它本身的值而是它对应的每个位置上的数字）是： 1\ 0\ 0\ 0

    对于第二个 2，insert(2,1)； 此时树状数组表示的每个数字是 1\ 1\ 0\ 0\

    对于第三个 1 ，因为之前出现过 1 了，因此首先把那个 1 所在的位置删掉 insert(1,-1) ,然后在把它加进来 insert(3,1) 。此时每个数字是 0\ 1\ 1\ 0

    如果此时有一个询问 [2,3] ，那么直接求 sum(3)-sum(2-1)=2 就是答案。

Trie (字典树)

  • 用于存储若干个字符串

实现

struct Trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int pos = 0;
    for (int i = 0; i < l; ++i) {
      int c = s[i] - 'a';
      if (!nex[pos][c]) nex[pos][c] = ++cnt;  // 如果没有，就添加结点
      pos = nex[pos][c];
    }
    exist[pos] = 1;
  }

  bool find(char *s, int l) {  // 查找字符串
    int pos = 0;
    for (int i = 0; i < l; ++i) {
      int c = s[i] - 'a';
      if (!nex[pos][c]) return 0;
      p = nex[pos][c];
    }
    return exist[pos];
  }
};

eg1 : P2922 [USACO08DEC] Secret Message G

solution :

  • 即求每条密码与几条信息有公共前缀

  • 那么我们可以用信息构建出一颗 Trie ，把每条密码当作查询的字符串。

  • 考虑字典树的构建过程：

    如果该单词结尾处下还有字符串，那么下面的字符串肯定也与该密码有着相同前缀。于是我们可以在构建过程中记录下经过每个节点的单词数，直接计算即可。

0/1 Trie

  • 用来维护一些数字的异或和，支持修改（删除 + 重新插入），和全局加一（即：让其所维护所有数值递增 1，本质上是一种特殊的修改操作）。

  • 插入 & 删除

如果要维护异或和，我们 只需要 知道某一位上 0 和 1 个数的 奇偶性 即可，也就是对于数字 1 来说，当且仅当这一位上数字 1 的个数为奇数时，这一位上的数字才是 1 ，请时刻记住这段文字：如果只是维护异或和，我们只需要知道某一位上 1 的数量即可，而不需要知道 trie 到底维护了哪些数字。

对于每一个节点，我们需要记录以下三个量：

  • ch[o][0/1] 指节点 o 的两个儿子，$ch[o][0]$ 指下一位是 $0$，同理 ch[o][1] 指下一位是 $1$。
  • w[o] 指节点 o 到其父亲节点这条边上数值的数量（权值）。每插入一个数字 x ， x 二进制拆分后在 Trie 上 路径的权值都会 +1 。
  • xorv[o] 指以 o 为根的子树维护的异或和。

具体维护结点的代码如下所示。

eg 2 : 树上异或

给定一棵 n 个点的树, 边有边权 a_1 到 a_n , T 次询问给定 i 和 k 求 i 到根节点上与 k 异或的最大值

solution :

  • 离线询问

  • 在 DFS 的过程中逐个处理询问

  • DFS 维护从根到当前节点的路径上的边构成的 0 / 1 Trie , 当前节点有记载一个询问时, 拿 k

在 Tire 上跑. 从高到低为贪心， 走到叶子即得答案

  • O(32(m + n))

eg3 : P4551 最长异或路径

solution :

  • 预处理每个节点到根的异或和
  • 同树上异或

eg4 : P5149 会议座位

solution :

  • 即求逆序对
  • 只不过数字换成了字符串
  • 咕咕咕 ~

小组成员: 邵品渊，邵品砚，蒋佳成，顾天泽，马天翔，陈继禹

3 个赞
2

大佬太强了

3

比syx都强！！