Tony.Lin 的小屋

链表

单向链表

struct Node
{
    int value;
    Node *next;
};
void insertNode(int i, Node *p)
{
    Node *node = new Node;
    node->value = i;
    node->next = p->next;
    p->next = node;
}
void insertNodeCircle(int i, Node *p)
{
    Node *node = new Node;
    node->value = i;
    node->next = NULL;
    if (p == NULL)
    {
        p = node;
        node->next = node;
    }
    else
    {
        node->next = p->next;
        p->next = node;
    }
}
void deleteNode(Node *p)
{
    p->value = p->next->value;
    Node *t = p->next;
    p->next = p->next->next;
    delete t;
}

双向链表

struct Node
{
    int value;
    Node *left;
    Node *right;
};
void insertNode(int i, Node *p)
{
    Node *node = new Node;
    node->value = i;
    if (p == NULL)
    {
        p = node;
        node->left = node;
        node->right = node;
    }
    else
    {
        node->left = p;
        node->right = p->right;
        p->right->left = node;
        p->right = node;
    }
}
void deleteNode(Node *&p)
{
    p->left->right = p->right;
    p->right->left = p->left;
    Node *t = p;
    p = p->right;
    delete t;
}

树状数组

原理

用大节点表示小节点信息，查询时查询大节点+剩余的小节点。例如计算区间和时，只要计算区间内可包括的大区间+不能包括的小区间。

查询管理区间使用 lowbit
（lowbit 指一个数二进制表示中最低位 1 的位置，可表示这个位置管理的元素总数）

区间加&区间求和

维护序列 a，差分数组 b，a 的前缀 r 求和，即为 $\sum ^{r}_{i=1} {a_i}$ ，由差分数组定义得 $a_i=\sum ^{i}_{j=1} {b_j}$

推导：

\begin{aligned} &\sum_{i=1}^{r} a_i\\=&\sum_{i=1}^r\sum_{j=1}^i b_j\\=&\sum_{i=1}^r b_i\times(r-i+1) \\=&\sum_{i=1}^r b_i\times (r+1)-\sum_{i=1}^r b_i\times i \end{aligned}

而区间和可由两个前缀相减得到，所以只要维护两个树状数组 $\sum b_i$ 和 $\sum i \times b_i$ 就可以实现区间求和

int t1[MAXN], t2[MAXN], n;

//区间加，区间求和
inline int lowbit(int x)
{
    return x & (-x);
}

void add(int k, int v)
{
    int v1 = k * v;
    while (k <= n)
    {
        t1[k] += v, t2[k] += v1;
        k += lowbit(k);
    }
}

int getsum(int *t, int k)
{
    int ret = 0;
    while (k)
    {
        ret += t[k];
        k -= lowbit(k);
    }
    return ret;
}

void add1(int l, int r, int v)
{
    add(l, v), add(r + 1, -v); //区间加差分为两个前缀和
}

long long getsum1(int l, int r)
{
    return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
           (getsum(t2, r) - getsum(t2, l - 1));
}

技巧：

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(log n)查询第 k 大/小元素

将所有数字看成一个可重集合，即定义数组 a 表示值 i 的元素在整个序列重出现了 $a_i$ 次。找第 k 大就是找到最小的 x 恰好满足 $\sum_{i=1}^{x}a_i \geq k$

考虑算法：如果已经找到 x 满足 $\sum_{i=1}^{x}a_i \le k$ ，考虑能不能让 x 继续增加，使其仍然满足这个条件。找到最大的 x 后，x+1 就是所需要的值。在树状数组中节点根据 2 的幂划分，每次扩大 2 的幂的长度。令 sum 表示当前的 x 所代表的前缀和，有如下算法找到最大的 x：

1.求出 $depth=\left \lfloor \log_2n \right \rfloor$

2.计算 $t=\sum_{i=x+1}^{x+2^{depth}}a_i$

3.如果 $sum+t \le k$ ，则此时扩展成功，将 $2^depth$ 累加到 x 上；否则扩展失败，不对 x 进行操作

4.将 depth-1，回到步骤 2，直到 depth=0

int kth(int k)
{
    int cnt = 0, ret = 0;
    for (int i = log2(n); ~i; --i) //i即为depth
    {
        ret += 1 << i; //扩展
        if (ret >= n || cnt + t[ret] >= k)
            ret -= 1 << i; //扩展失败后还原
        else
            cnt += t[ret]; //扩展成功后更新之前求和的值
    }
    return ret + 1;
}

时间戳优化

应对多组数据的技巧。如果每次输入新数据都清空数组有可能超时。因此使用 tag 标记，存储当前节点上次使用的时间（即最近一次是被第几组数据使用）。每次操作时判断这个位置 tag 中的时间和当前时间是否相同，就可以判断这个位置是 0 还是数组中的值。

int Tag, tag[MAXN];
void reset()
{
    ++Tag;
}
void add(int k, int v)
{
    while (k <= n)
    {
        if (tag[k] != Tag)
            t[k] = 0;
        t[k] += v, tag[k] = Tag;
        k += lowbit(k);
    }
}
int getsum(int k)
{
    int ret = 0;
    while (k)
    {
        if (tag[k] == Tag)
            ret += t[k];
        k -= lowbit(k);
    }
    return ret;
}

线段树

线段树用于维护区间信息。在 O(log N)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，区间最大值，区间最小值）等操作。

基本结构与建树

把长度不为 1 的区间划分为左右两个区间递归求解，把线段划分为树形结构，通过合并左右两区间的信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

具体而言，设线段树的根节点编号为 1，用数组 d 来保存我们的线段树， $d_i$ 用来保存线段树上编号为 i 的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。

$d_i$ 的左儿子节点就是 $d_{2*i}$ ,右儿子节点就是 $d_{2*i+1}$ 。如果 $d_i$ 表示的是区间 $[s,t]$ ，则 $d_i$ 的左儿子节点表示的就是区间 $[ s, \frac{s+t}{2} ]$ , $d_i$ 的右儿子表示的是区间 $[ \frac{s+t}{2} +1,t ]$ 。

实现时，考虑递归建树。设当前根节点 p，如果根节点管辖的区间长度为 1，则可以直接根据 a 数组上相应位置的值初始化该节点。否则将该区间从中点处分割为两个子区间，分别进入左右节点递归建树，最后合并两个字节点的信息。

void build(int s, int t, int p)
{
    //对[s,t]区间建立线段树，当前根的编号为p
    if (s = t)
    {
        d[p] = a[s];
        return;
    }
    int m = s + ((t - s) >> 1);
    //移位运算符的优先级小于加减法，所以加上括号
    //如果写成（s+t）>>1 可能会超出int范围
    build(s, m, p * 2), build(m + 2, t, p * 2 + 1);
    //递归对左右区间建树
    d[p] = d[p * 2] + d[p * 2 + 1];
}

线段树空间：若有 n 个叶子节点，则数组范围最大为 $2^{\left\lceil\log{n}\right\rceil+1}$ ,可以直接设为 4n

线段树的区间查询

比如求区间总和，区间最大/最小值等操作。

一般地，如果要查询的区间是 $[l,r]$ ，则可以将其拆成最多为 O(log n)个极大的区间，合并这些区间即可求出 $[l,r]$ 的答案。

int getsum(int l, int r, int s, int t, int p)
{
    //[l,r]为查找区间，[s,t]为当前节点包含的区间，p为当前节点的编号
    if (l <= s && t <= r)
    {
        return d[p];
    } //当前区间为询问区间的子集时直接返回当前区间的和
    int m = s + ((t - s) >> 1), sum = 0;
    if (l <= m)
        sum += getsum(l, r, s, m, p * 2);
    //如果左儿子代表的区间[l,m]与询问区间有交集，则递归查询左儿子
    if (r > m)
        sum += getsum(l, r, m + 1, t, p * 2 + 1);
    //如果右儿子代表的区间[m+1,r]与询问区间有交集，则递归查询右儿子
    return sum;
}

线段树的区间修改与 Lazy Tag

如果修改区间，则区间内节点都需要遍历修改，容易超时，因而引入“Lazy Tag”。

简而言之，就是通过延迟对节点信息的更改减少不必要的操作次数。每次执行修改时，用打标记的方法表明该节点对应的区间在某一次操作中被更改，但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

void update(int l, int r, int c, int s, int t, int p)
{
    //[l,r]为修改区间，c为被修改的元素的变化量，[s,t]为当前节点包含的区间
    //p为当前节点的编号
    if (l <= s && t <= r)
    {
        d[p] += (t - s + 1) * c, b[p] = c;
        return;
    } //当前区间为修改区间的子集时直接修改当前节点的值，然后打标记，结束修改
    int m = s + ((t - s) >> 1);
    if (b[p] && s != t)
    {
        //如果当前节点的Lazy Tag为空，则更新当前节点两个字节点的值和Lazy Tag
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p]; //将标记下传给子节点
        b[p] = 0;                               //清空当前节点的标记
    }
    if (l <= m)
        update(l, r, c, s, m, p * 2);
    if (r > m)
        update(l, r, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p)
{
    //[l,r]为查询区间，[s,t]为当前节点包含的区间，p为当前节点的编号
    if (l <= s && t <= r)
        return d[p];
    //当前区间为询问区间的子集时直接返回当前区间的和
    int m = s + ((t - s) >> 1);
    if (b[p])
    {
        //如果当前节点的LazyTag非空，则更新当前节点两个字节点的值和LazyTag
        d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
        b[p * 2] += b[p], b[p * 2 + 1] += b[p]; //将标记下传给子节点
        b[p] = 0;                               //清空当前节点的标记
    }
    int sum = 0;
    if (l <= m)
        sum = getsum(l, r, s, m, p * 2);
    if (r > m)
        sum += getsum(l, r, m + 1, t, p * 2 + 1);
    return sum;
}

如果是实现区间内修改某一个值，代码如下

void update(int l, int r, int c, int s, int t, int p)
{
    if (l <= s && t <= r)
    {
        d[p] = (t - s + 1) * c, b[p] = c;
        return;
    }
    m = s + ((t - s) >> 1);
    if (b[p])
    {
        d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
        b[p * 2] = b[p * 2 + 1] = b[p];
        b[p] = 0;
    }
    if (l <= m)
        update(l, r, c, s, m, p * 2);
    if (r >= m)
        update(l, r, c, m + 1, t, p * 2 + 1);
    d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p)
{
    if (l <= s && t <= r)
        return d[p];
    int m = s = +((t - s) >> 1);
    if (b[p])
    {
        d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
        b[p * 2] = b[p * 2 + 1] = b[p];
        b[p] = 0;
    }
    int sum = 0;
    if (l <= m)
        sum = getsum(l, r, s, m, p * 2);
    if (r > m)
        sum += getsum(l, r, m + 1, t, p * 2 + 1);
    return sum;
}

优化

在叶子节点处无需下方 Lazy Tag，所以 Lazy Tag 可以不下传到叶子节点。

下放 Lazy Tag 可以写一个函数 pushdown，从儿子节点更新当前节点也可以写一个专门的函数 maintain（或者 pushup），降低代码编写难度。

标记永久化：如果确定 Lazy Tag 不会在中途被加到溢出（超过表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传 Lazy Tag，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体处理与题目特性相关