算法学习:基础数据结构

算法学习:基础数据结构

单调队列、树状数组、差分队列与线段树。

单调队列

一个具有单调性的队列,具体操作为:(单调增的队列)

  1. 若队列为空,将A[i]从对队尾入队。
  2. 若队列不为空,将比A[i]大的元素从队尾弹出,然后把A[i]入队。
  3. 若队列不为空且A[i]大于队尾,则直接从队尾把A[i]入队。

树状数组

以前的板子有,先略过(注意提醒博主补上)

差分队列(区间修改点查询的树状数组)

树状数组本身是点修改区间查询的,对于原本的模式他有两个数组:a[],用以记录原本的数组序列;b[]用以记录形成的树状数组。

将这两个数组角色翻转,用b[]来表示原本的、要被修改的数组,用a[]记录辅助的,用以查询的数组。则按以下方法构建:

  • 有已知数组a[],用以记录原数组值。
  • 引入差分数组b[],定义$b[i] = a[i] - a[i-1]$。可以得到 $a[i] = b[1] + b[2] + b[3] + \cdots+b[i] $。
  • 引入树状数组a[]维护b[]的前缀和。

由以上关系,当我需要对a[]的区间 $[l,r]$ 进行修改,全部加上k值,只需要将b[l] += kb[r + 1]-= k即可实现。Update后对a[i]具体值直接进行点查询。

二维树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int s[105][105],N,M;
int lowbit(int i){
return i & -i;
}
void set(int i, int j, int x){
for (int ii = i;ii <= N;ii+= lowbit(ii)){
for(int jj = j;j <= M;jj += lowbit(jj)){
s[ii][jj] += x;
}
}
}
int get(int i, int j){
int ans = 0;
for (int ii = i;ii > 0;ii -= lowbit(ii))
for(int jj = j;jj > 0;jj -= lowbit(jj))
ans += a[ii][jj];
return ans;
}

线段树

1563250811851

线段树是一种如上图所示的数据结构,将一个长度较长的数组按照树的结构不断二分形成如图结构。

线段树的解题关键

  • 如何通过子节点来推出父节点的信息?每一个节点都需要哪些信息?
  • 在区间更新中,我如何通过父节点的增值内容推出子节点的增值内容以便在进行区间查询时得到正确的结果?(Lazy Tag 的设定)

线段树的存储结构

  • 建立数组tree[],数组下标从1开始,其中tree[1]为根节点,整体的统计信息、最终答案都将会存在tree[1]中。
  • 对于任意一个节点tree[x],它的左节点信息存储在tree[2 * x]中,右节点信息存储在tree[2 * x + 1]中。

线段树的操作函数

  • build()函数:用于建立整个线段树。

    • 通过递归不断将二分分解原区间,直到找到叶节点所在位置(长度为1的区间)

    • 将具体值放在这个叶节点,然后不断向上回溯修改所有父节点的值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void build(int l, int r, int root){
    if(l == r){
    num[root] = 1;
    return;
    }

    // [l, mid]:左子树 [mid+1, r]:右子树
    int mid = (l + r) / 2;
    build(l, mid, root*2);
    build(mid+1, r, root*2 + 1);
    push_up(root);
    // 对于这个根节点,先把左右子树都算出来了,再来更新它的值。
    // 沿路回溯。回溯到的点root,都是被[la, rb]或其子区间影响到的点,边回溯边更新。
    }

    // 调用 build(1, N, 1);
  • update()函数:修改(更新)函数,分为单点更新和区间更新。

    • 单点更新的update()函数:

      • 由根节点 $1$ 向下递归,找到对应的叶节点;
      • 修改叶结点的值;
      • 向上返回,在函数返回的过程中,更新路径上的节点的统计信息。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void upgrade(int p, int val, int l, int r, int root){
      // 单点更新,值增加增加val
      if (l == r){
      num[root] += val;
      return;
      }

      int mid = (l + r) / 2;
      if (p > mid) // 如果p > 当前区间的中点, 说明我想找的[p, p]区间,在右半边
      upgrade(p, val, mid+1, r, root * 2 + 1);
      else upgrade(p, val, l , mid, root * 2);

      //沿路返回,回溯到的点root, 都是被[p, p]区间影响到的点,边回溯边更新
      num[root] = num[root * 2] + num[root * 2 + 1];
      }
  • 区间更新的update()函数:

    • 与单点更新的区别在于,区间修改在理论上是需要向下修改的(因为父区间变化,子区间也会变化)
    • 为减少操作的复杂度,引入lazy_tag,这样我们暂时不更新下面的子节点,而是在需要用到子节点的时候再顺着这个标签向下更新子节点(需要用到push_down()函数)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    void update(int la, int rb, int l, int r, int val, int root){
    /* la、lb为需要更新的区间的左端点(不发生变化)
    l、r为当前区间的左、右端点(会随着递归而发生更新)
    root为当前[l, r]对应的根存储位置(随递归更新)
    更改区间内值为val
    */
    // 如果本次所看的区间,整个就包含在所要查询的区间内。
    if(la <= l && rb >= r){
    num[root] = (r - l + 1) * val; // 把本区间的num更新为正确值
    lazy[root] = val; // 增加lazy标记,表示本区间的Sum正确,子区间的Sum 任然需要根据lazy的值来调整。
    return;
    }
    push_down(root, r - l + 1);
    //继续递归前,先将当前root的标记向下传,从而保证再计算root时,他的左右两个自述都已经是正确的值,左右两个子树都不存在lazy更新延迟,都已经更新好了。
    int mid = (l + r) / 2;
    if (la <= mid){
    update(la, rb, l, mid, val, root * 2);
    }
    if (rb > mid){
    update(la, rb, mid + 1, r, val, root * 2 + 1);
    }

    push_up(root);
    }
  • push_up()函数:父节点回溯更新函数

    • 这个函数的目的是,已经知道了两个子节点的信息,利用这个函数推出父节点的信息。
    • 前提是两个节点的信息已经是正确了的、更新过了的
    1
    2
    3
    void push_up(int root){
    num[root] = num[root * 2] + num[root * 2 + 1];
    }
  • push_down()函数:区间更新,将lazy_tag向下推。

    • 更新左右节点的 Lazy 值,也就是:把父节点root上面的 Lazy 标记,下推到两个子节点上
    • 依据 Lazy Tag 的定义,更新左右节点的num值,使左右子节点的值成为被更新过的、正确的值
    • 把父节点的 Lazy Tag 值清空。因为 Lazy Tag 已经下推,就向上查询来看,父节点自身的 Lazy Tag 已经不再需要。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void push_down(int root, int len){
    if (lazy[root] == 0)
    return;
    lazy[root * 2] = lazy[root];
    lazy[root * 2 + 1] = lazy[root];

    num[root * 2] = lazy[root * 2] * (len - (len) / 2);
    num[root * 2 + 1] = lazy[root * 2 + 1] * ((len) / 2);

    lazy[root] = 0;
    }

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×