基础数据结构学习笔记

2024-03-16 11:18:16

开坑与2022.2.16
$\text{update1}$:新增了一些关于线段树的拓展内容-2022.3.2

树状数组

最近突然发现树状数组不会打了。

作为立志成为小常数选手的我，怎么能忘记这个数据结构呢？

复习一下：

纯手打(一边写博客，一边打的)：

#include <bits/stdc++.h>
using namespace std;

int n , m , t[500010];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

int lowbit(int x)
{
    return x & (-x);
}

void update(int x , int y)
{
    while(x <= n)
    {
        t[x] += y;
        x += lowbit(x);
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n;i++) update(i , read());
    for(int i = 1;i <= m;i++)
    {
        int opt = read() , x = read() , k = read();
        if(opt == 1) update(x , k);
        else cout << ask(k) - ask(x - 1) << endl;
    }
    return 0;
}

打了七八分钟，速度好像慢了。

下一个：

【模板】树状数组 2

#include <bits/stdc++.h>
using namespace std;

int n , m , a[500010] , t[500010];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

int lowbit(int x)
{
    return x & (-x);
}

void update(int x , int y)
{
    while(x <= n)
    {
        t[x] += y;
        x += lowbit(x);
    }
}

int ask(int x)
{
    int ans = 0;
    while(x)
    {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i <= n;i++) update(i , a[i] - a[i - 1]);
    for(int i = 1;i <= m;i++)
    {
        int opt = read() , x = read();
        if(opt == 1) 
        {
            int y = read() , k = read();
            update(x , k) , update(y + 1 , -k);
        }
        else cout << ask(x) << endl;
    }
    return 0;
}

在上一个的基础上改的，花了四分零四秒。

有图为证：

一些拓展的小知识

树状数组套主席树

如果不知道主席树可以移步$ My~Blog$。

例题。

这道题花了我一个上午两个半小时，十二遍评测，才卡过去了。

实测我的常数还是比较大(跑了将近两秒)。

我们考虑用经典的树状数组套主席树。

0. 一些基础的概念

为什么树状数组能套主席树。

每一颗主席树的结构相同，可以用树状数组来统计前缀和。

为什么要用树状数组套主席树。

树状数组常数小！！！

1. 初始化

要注意，树状数组套主席树的方式非常炸空间，所以数组一定要开准一点(随随便便就会$MLE$和$RE$)。

const int maxn = 5e4 + 5;
//注意+10有可能会MLE

int n, m, a[maxn], b[maxn << 1], id[maxn];
int q, cnt, tot1, tot2, tmp1[maxn], tmp2[maxn];

struct edge
{
    int l, r, sum;
} t[maxn * 101];
//我也不知道为什么开100倍会RE最后一个点

struct question
{
    int opt, l, r, k;
} ql[maxn];
//离线存问题

2. 读入

我们需要进行离线，在线应该不行(也可能是我太菜了)。

n = read(), m = read(), q = n;
for (int i = 1; i <= n; i++)
    a[i] = b[i] = read();
for (int i = 1; i <= m; i++)
{
    ql[i].opt = read(), ql[i].l = read(), ql[i].r = read();
    if (ql[i].opt != 3)
        ql[i].k = read();
    else
        b[++q] = ql[i].r;
    if (ql[i].opt == 4 || ql[i].opt == 5)
        b[++q] = ql[i].k;
}

其中$~b~$数组就和主席树中的一样，统计权值，进行离散化。

3. 离散化

sort(b + 1, b + q + 1);
q = unique(b + 1, b + q + 1) - b - 1;
for (int i = 1; i <= n; i++)
{
    a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
    change(i, 1);
}

标准的离散化。

4. 修改

由于我们运用的是树状数组来统计主席树的前缀和，所以就有必不可少的 $lowbit$ 操作。

int lowbit(int x)
{
    return x & (-x);
}

第一个修改当然是用树状数组求出需要修改的主席树啦。

void change(int p, int k)
{
    for (int i = p; i <= n; i += lowbit(i))
    {
        update(id[i], a[p], k, 1, q);
    }
}

至于主席树内部的修改就比较无脑直接暴力用板子修就可以了。

void update(int &p, int x, int k, int l, int r)
{
    if (!p)
        p = ++cnt;
    if (l == r)
    {
        t[p].sum += k;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        update(t[p].l, x, k, l, mid);
    else
        update(t[p].r, x, k, mid + 1, r);
    t[p].sum = t[t[p].l].sum + t[t[p].r].sum;
}

5. 五个操作前的二分

我们发现，现在的$~b~$数组还存了修改后的值，所以为了保证离散化，在每一个询问的值，都要进行二分离散化。

6. 求区间第K大

这里和主席树板子差不多，只是变成了树状数组来统计前缀和。

int ask(int l, int r, int k)
{
    tot1 = 0, tot2 = 0;
    for (int i = r; i; i -= lowbit(i))
        tmp1[++tot1] = id[i];
    for (int i = l - 1; i; i -= lowbit(i))
        tmp2[++tot2] = id[i];
    return query(1, q, k);
}

两个$~tmp~$数组存的是需要统计的主席树编号，和树状数组求和操作相同。

int query(int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1, ans = 0;
    for (int i = 1; i <= tot1; i++)
        ans += t[t[tmp1[i]].l].sum;
    for (int i = 1; i <= tot2; i++)
        ans -= t[t[tmp2[i]].l].sum;
    if (k <= ans)
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].l;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].l;
        return query(l, mid, k);
    }
    else
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].r;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].r;
        return query(mid + 1, r, k - ans);
        //注意减ans
    }
}

主席树内部操作和板子也差不多。

一边求出左子树有多少个数，在不断转移需要求的主席树编号。

应该还算好理解。

7. 求区间K的排名

这个和上一个操作相差无几，只需要改几个地方就可以了。

int query_rank(int l, int r, int k)
{
    if (l == r)
        return 0;
    //这里返回的是0；
    //因为不需要将自己统计进去
    int mid = (l + r) >> 1, ans = 0;

    if (k <= mid)
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].l;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].l;
        return query_rank(l, mid, k);
    }
    else
    {
        for (int i = 1; i <= tot1; i++)
            ans += t[t[tmp1[i]].l].sum;
        for (int i = 1; i <= tot2; i++)
            ans -= t[t[tmp2[i]].l].sum;
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].r;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].r;
        return ans + query_rank(mid + 1, r, k);
        //这里不用减ans;
    }
}

int ask_rank(int l, int r, int k)
{
    tot1 = 0, tot2 = 0;
    for (int i = r; i; i -= lowbit(i))
        tmp1[++tot1] = id[i];
    for (int i = l - 1; i; i -= lowbit(i))
        tmp2[++tot2] = id[i];
    return query_rank(1, q, k) + 1;
    //注意排名要加一
}

8. 求区间前驱后继

既然已经有了上面两个操作。

那么这个操作只需要上面两个操作和一些特判就可以了。

读者不妨自己思考一下。

int ask_qian(int l, int r, int k)
{
    int x = ask_rank(l, r, k) - 1;
    if (x == 0)
        return 0;
    return ask(l, r, x);
}

int ask_hou(int l, int r, int k)
{
    if (k == q)
        return q + 1;
    int x = ask_rank(l, r, k + 1);
    if (x == r - l + 2)
        return q + 1;
    return ask(l, r, x);
}

这样，这个题你就切掉了。

Code

$~vscode~$格式化后$~4.56KB~$

格式化前$~3.6KB~$

不算特别长。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 5;
int n, m, a[maxn], b[maxn << 1], id[maxn];
int q, cnt, tot1, tot2, tmp1[maxn], tmp2[maxn];

struct edge
{
    int l, r, sum;
} t[maxn * 101];

struct question
{
    int opt, l, r, k;
} ql[maxn];

int read()
{
    int asd = 0, qwe = 1;
    char zxc;
    while (!isdigit(zxc = getchar()))
        if (zxc == '-')
            qwe = -1;
    while (isdigit(zxc))
        asd = asd * 10 + zxc - '0', zxc = getchar();
    return asd * qwe;
}

int lowbit(int x)
{
    return x & (-x);
}

void update(int &p, int x, int k, int l, int r)
{
    if (!p)
        p = ++cnt;
    if (l == r)
    {
        t[p].sum += k;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        update(t[p].l, x, k, l, mid);
    else
        update(t[p].r, x, k, mid + 1, r);
    t[p].sum = t[t[p].l].sum + t[t[p].r].sum;
}

void change(int p, int k)
{
    for (int i = p; i <= n; i += lowbit(i))
    {
        update(id[i], a[p], k, 1, q);
    }
}

int query(int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1, ans = 0;
    for (int i = 1; i <= tot1; i++)
        ans += t[t[tmp1[i]].l].sum;
    for (int i = 1; i <= tot2; i++)
        ans -= t[t[tmp2[i]].l].sum;
    if (k <= ans)
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].l;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].l;
        return query(l, mid, k);
    }
    else
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].r;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].r;
        return query(mid + 1, r, k - ans);
    }
}

int ask(int l, int r, int k)
{
    tot1 = 0, tot2 = 0;
    for (int i = r; i; i -= lowbit(i))
        tmp1[++tot1] = id[i];
    for (int i = l - 1; i; i -= lowbit(i))
        tmp2[++tot2] = id[i];
    return query(1, q, k);
}

int query_rank(int l, int r, int k)
{
    if (l == r)
        return 0;
    int mid = (l + r) >> 1, ans = 0;

    if (k <= mid)
    {
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].l;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].l;
        return query_rank(l, mid, k);
    }
    else
    {
        for (int i = 1; i <= tot1; i++)
            ans += t[t[tmp1[i]].l].sum;
        for (int i = 1; i <= tot2; i++)
            ans -= t[t[tmp2[i]].l].sum;
        for (int i = 1; i <= tot1; i++)
            tmp1[i] = t[tmp1[i]].r;
        for (int i = 1; i <= tot2; i++)
            tmp2[i] = t[tmp2[i]].r;
        return ans + query_rank(mid + 1, r, k);
    }
}

int ask_rank(int l, int r, int k)
{
    tot1 = 0, tot2 = 0;
    for (int i = r; i; i -= lowbit(i))
        tmp1[++tot1] = id[i];
    for (int i = l - 1; i; i -= lowbit(i))
        tmp2[++tot2] = id[i];
    return query_rank(1, q, k) + 1;
}

int ask_qian(int l, int r, int k)
{
    int x = ask_rank(l, r, k) - 1;
    if (x == 0)
        return 0;
    return ask(l, r, x);
}

int ask_hou(int l, int r, int k)
{
    if (k == q)
        return q + 1;
    int x = ask_rank(l, r, k + 1);
    if (x == r - l + 2)
        return q + 1;
    return ask(l, r, x);
}

signed main()
{
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    n = read(), m = read(), q = n;
    for (int i = 1; i <= n; i++)
        a[i] = b[i] = read();
    for (int i = 1; i <= m; i++)
    {
        ql[i].opt = read(), ql[i].l = read(), ql[i].r = read();
        if (ql[i].opt != 3)
            ql[i].k = read();
        else
            b[++q] = ql[i].r;
        if (ql[i].opt == 4 || ql[i].opt == 5)
            b[++q] = ql[i].k;
    }
    sort(b + 1, b + q + 1);
    q = unique(b + 1, b + q + 1) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
        change(i, 1);
    }
    b[0] = -2147483647, b[q + 1] = 2147483647;
    for (int i = 1; i <= m; i++)
    {
        if (ql[i].opt == 1)
            ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", ask_rank(ql[i].l, ql[i].r, ql[i].k));
        if (ql[i].opt == 2)
            printf("%lld\n", b[ask(ql[i].l, ql[i].r, ql[i].k)]);
        if (ql[i].opt == 3)
            change(ql[i].l, -1), a[ql[i].l] = lower_bound(b + 1, b + q + 1, ql[i].r) - b, change(ql[i].l, 1);
        if (ql[i].opt == 4)
            ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", b[ask_qian(ql[i].l, ql[i].r, ql[i].k)]);
        if (ql[i].opt == 5)
            ql[i].k = lower_bound(b + 1, b + q + 1, ql[i].k) - b, printf("%lld\n", b[ask_hou(ql[i].l, ql[i].r, ql[i].k)]);
    }
    return 0;
}

权值线段树

权值线段树，一个可以动态维护区间的第$~k~$小（反之同理）的数据结构。

在线段树的基础上优化而来，代码实现比较简单。

支持单点修改。

时间复杂度:修改和查询均为$O(\log_{n})$

大致思路

将每一个节点维护原序列的权值。

记录每个区间每个数的出现次数。

因此建树是可以只需要维护左右区间。

void build(int p , int l , int r)
{
    t[p].l = l , t[p].r = r;
    if(l == r) return;
    build(p * 2 , l , (l + r) / 2);
    build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}

注意调用入口的范围是你题目序列里的最大值和最小值。

例如题目规定：

$a_{i} \leqslant 1e5$

那么调用入口为：

build(1 , 1 , 100000);

将序列放入线段树内需要修改操作。

这里呈现的代码是要维护区间的第$~k~$小和区间的前$~k~$小之和。

void update(int p , int k)
{
    t[p].sum += k , t[p].num++;
    if(t[p].l == t[p].r) return;
    if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k);
    else update(p * 2 , k);
}

那么，区间求值也很好写。

求区间的前$~k~$小之和：


int ask(int p , int k)
{
    if(t[p].l == t[p].r) return t[p].sum / t[p].num * k;
    if(k > t[p * 2].num) return t[p * 2].sum + ask(p * 2 + 1 , k - t[p * 2].num);
    else return ask(p * 2 , k);
}

求区间的第$~k~$小：


int ask(int p , int k)
{
    if(t[p].l == t[p].r) return t[p].sum / t[p].num;
    if(k > t[p * 2].num) return ask(p * 2 + 1 , k - t[p * 2].num);
    else return ask(p * 2 , k);
}

例题：稳定桌（区间的前$~k~$小之和的运用）。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , top , ans , l[100110] , d[100110] , sum[100110] , num[100110];
vector<int> ton[100110];

struct edge
{
    int l , r , sum , num;
}t[800080];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

void update(int p , int k)
{
    t[p].sum += k , t[p].num++;
    if(t[p].l == t[p].r) return;
    if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k);
    else update(p * 2 , k);
}

void build(int p , int l , int r)
{
    t[p].l = l , t[p].r = r;
    if(l == r) return;
    build(p * 2 , l , (l + r) / 2);
    build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}

int ask(int p , int k)
{
    if(t[p].l == t[p].r) return t[p].sum / t[p].num * k;
    if(k > t[p * 2].num) return t[p * 2].sum + ask(p * 2 + 1 , k - t[p * 2].num);
    else return ask(p * 2 , k);
}

signed main()
{
    n = read() , ans = 1e11;
    for(int i = 1;i <= n;i++) l[i] = read();
    for(int i = 1;i <= n;i++) d[i] = read() , ton[l[i]].push_back(d[i]);
    build(1 , 1 , 100000);
    for(int i = 100000;i >= 1;i--)
    {
        sum[i] = sum[i + 1] , num[i] = num[i + 1];
        int len = ton[i].size();
        if(len == 0) continue;
        for(int j = 0;j < len;j++) sum[i] += ton[i][j] , num[i]++;
    }
    for(int i = 1;i <= 100000;i++)
    {
        int len = ton[i].size() , l = 0;
        if(len == 0) continue;
        int x = n - num[i] , y = x - len + 1;
        if(y <= 0) ans = min(ans , sum[i + 1]);
        else
        {
            l = ask(1 , y) + sum[i + 1];
            ans = min(l , ans);
        }
        for(int j = 0;j < len;j++) update(1 , ton[i][j]);
    }
    cout << ans;
    return 0;
}

$10.30$ 新增：

发现一道模板题：

P3369 【模板】普通平衡树

是的，这道题我们也可以用权值线段树跑过去。

实测:

权值线段树 298ms。

无旋treap 407ms。

常数的优势瞬间体现出来了。

虽然没有红黑树和平板电视跑得快。

但谁会拒绝好写好调代码又短的权值线段树呢。

代码实现比较简单，还不到一百行。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , q , b[100010];
pair<int , int> a[100010];

struct edge
{
    int l , r , num;
}t[800080];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

void update(int p , int k , int x)
{
    t[p].num += x;
    if(t[p].l == t[p].r) return;
    if(k >= t[p * 2 + 1].l) update(p * 2 + 1 , k , x);
    else update(p * 2 , k , x);
}

void build(int p , int l , int r)
{
    t[p].l = l , t[p].r = r;
    if(l == r) return;
    build(p * 2 , l , (l + r) / 2);
    build(p * 2 + 1 , (l + r) / 2 + 1 , r);
}

int ask(int p , int k)
{
    if(t[p].l == t[p].r) return t[p].l;
    if(k > t[p * 2].num) return ask(p * 2 + 1 , k - t[p * 2].num);
    else return ask(p * 2 , k);
}

int ask_rank(int p , int l , int r)
{
    if(l <= t[p].l && t[p].r <=r) return t[p].num;
    int mid = (t[p].l + t[p].r) >> 1 , ans = 0;
    if(l <= mid) ans += ask_rank(p << 1 , l , r);
    if(r > mid) ans += ask_rank(p << 1 | 1 , l , r);
    return ans;
}

int ask_qian(int x)
{
    int a = ask_rank(1 , 1 , x - 1);
    return ask(1 , a);
}

int ask_hou(int x)
{
    int a = ask_rank(1 , 1 , x) + 1;
    return ask(1 , a);
}

signed main()
{
    n = read();
    for(int i = 1;i <= n;i++) 
    {
        a[i].first = read() , a[i].second = read();
        if(a[i].first != 4) b[++q] = a[i].second;
    }
        
    sort(b + 1 , b + q + 1);
    q = unique(b + 1 , b + q + 1) - b - 1;
    build(1 , 1 , q);
    for(int i = 1;i <= n;i++)
    {
        int x = a[i].first , y = a[i].second;
        if(x != 4) y = lower_bound(b + 1 , b + q + 1 , y) - b;
        if(x == 1) update(1 , y , 1);
        if(x == 2) update(1 , y , -1);
        if(x == 3) 
        {
            if(y == 1) cout << 1 << endl;
            else cout << ask_rank(1 , 1 , y - 1) + 1 << endl;
        }
        if(x == 4) cout << b[ask(1 , y)]  << endl;
        if(x == 5) cout << b[ask_qian(y)] << endl;
        if(x == 6) cout << b[ask_hou(y)] << endl;
    }
    return 0;
}

主席树

主席树，即维护任意区间第$~k~$大的数据结构。

支持单点修改和区间查询。

大致思路

主席树的思想为对序列的每一个前缀进行构造权值线段树维护。

即可持久化线段树。

0. 初始化

可以发现，由于空间复杂度问题，我们无法直接算出一个节点的左右儿子，所以均须记录。

int id[maxn];
//id为每一个前缀的线段树标号。

struct ST
{
    int l , r , sum;
    //l为左儿子标号，r为右儿子标号。
    //sum即权值线段树的num。
}t[maxn << 5];

//注意三十二倍空间

考虑到空间复杂度，以及每一道主席树题目的毒瘤程度。

我们需要离散化。


//基本的离散化。

sort(b + 1 ,  b + n + 1);
q = unique(b + 1 , b + n + 1) - b - 1;
build(id[0] , 1 , q);
for(int i = 1;i <= n;i++)
{
    int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
    id[i] = update(id[i - 1] , 1 , q , x);
}

1. 建树

由于我们无法直接得出左右儿子的标号，所以建树可以只统计$~id~$数组。

void build(int &p , int  l , int r)
{
    p = ++cnt;
    if(l == r) return;
    build(t[p].l , l , (l + r) / 2);
    build(t[p].r , (l + r) / 2 + 1 , r);
}

其中，$~cnt~$为线段树标号记录。

调用入口：

build(id[0] , 1 , q);

$~q~$为离散化后的总数。

2. 单点修改

与权值线段树相差无几，唯一区别是要在开一颗线段树。

int update(int p , int  l  ,int r , int k)
{
    int o = ++cnt; t[o] = t[p] , t[o].sum++;
    //开了一颗新的线段树。
    if(l == r) return o; int mid = (l + r) / 2;
    if(k <= mid) t[o].l = update(t[p].l , l , mid , k);
    else t[o].r = update(t[p].r , mid + 1 , r , k);
    return o;
}

3. 区间查询

思考一下，我们为什么维护的是前缀的线段树。

是不是跟前缀和有一点像。

它就是一个前缀和的作用。

因为每一个线段树的结构相同，所以具有可加可减性。

那么区间查询也和权值线段树很像了。

int ask(int u , int v , int  l , int  r , int k)
{
    int ans = 0 , mid = (l + r) / 2;
    int x = s[s[v].l].sum - s[s[u].l].sum;
    //和前缀和一样的操作。
    if(l == r) return l;
    if(x >= k) ans = ask(s[u].l , s[v].l , l , mid , k);
    else ans = ask(s[u].r , s[v].r , mid + 1 , r , k - x);
    return ans;
}

讲到现在，板子题就已经可以过了。

题目传送门

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n , m , q , cnt;
int a[maxn] , t[maxn] , b[maxn];

struct ST
{
    int l , r , sum;
}s[maxn << 5];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

void build(int &p , int l , int r)
{
    p = ++cnt;
    if(l == r) return;
    build(s[p].l , l , (l + r) / 2);
    build(s[p].r , (l + r) / 2 + 1 , r);
}

int update(int p , int  l , int r , int x)
{
    int o = ++cnt; s[o] = s[p] , s[o].sum++;
    if(l == r) return o; int mid = (l + r) / 2;
    if(x <= mid) s[o].l = update(s[o].l , l , mid , x);
    else s[o].r = update(s[o].r , mid + 1 , r , x);
    return o;
}

int ask(int u , int v , int  l , int  r , int k)
{
    int ans = 0 , mid = (l + r) / 2 , x = s[s[v].l].sum - s[s[u].l].sum;
    if(l == r) return l;
    if(x >= k) ans = ask(s[u].l , s[v].l , l , mid , k);
    else ans = ask(s[u].r , s[v].r , mid + 1 , r , k - x);
    return ans;
}

int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n;i++) a[i] = b[i] = read();
    sort(b + 1 , b + n + 1);
    q = unique(b + 1,  b + n + 1) - b - 1;
    build(t[0] , 1 , q);
    for(int i = 1;i<= n;i++)
    {
        int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
        t[i] = update(t[i - 1] , 1 , q , x);
    }
    for(int i = 1;i <= m;i++)
    {
        int l = read() , r = read() , k = read();
        cout << b[ask(t[l - 1] , t[r] , 1 , q , k)] << endl;
    }
    return 0;
}

同样的还有一道板子题。

题目传送门

这一道题是不是很好想。

只要该一下区间查询就可以了。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
int n , m , q , cnt;
int a[maxn] , id[maxn] , b[maxn];

struct ST
{
    int l , r , sum;
}t[maxn << 5];

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

void build(int &p , int  l , int r)
{
    p = ++cnt;
    if(l == r) return;
    build(t[p].l , l , (l + r) / 2);
    build(t[p].r , (l + r) / 2 + 1 , r);
}

int update(int p , int  l  ,int r , int k)
{
    int o = ++cnt; t[o] = t[p] , t[o].sum++;
    if(l == r) return o; int mid = (l + r) / 2;
    if(k <= mid) t[o].l = update(t[p].l , l , mid , k);
    else t[o].r = update(t[p].r , mid + 1 , r , k);
    return o;
}

int ask(int u , int v , int  l , int  r , int k)
{
    int mid = (l + r) / 2; 
    if(l == r) return l;
    int x = t[t[v].l].sum - t[t[u].l].sum , y = t[t[v].r].sum - t[t[u].r].sum;
    if(x > k) return ask(t[u].l , t[v].l , l , mid , k);
    if(y > k) return ask(t[u].r , t[v].r , mid + 1 , r , k);
    return 0;
}


int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n;i++) a[i] = b[i] = read();
    sort(b + 1 ,  b + n + 1);
    q = unique(b + 1 , b + n + 1) - b - 1;
    build(id[0] , 1 , q);
    for(int i = 1;i <= n;i++)
    {
        int x = lower_bound(b + 1 , b + q + 1 , a[i]) - b;
        id[i] = update(id[i - 1] , 1 , q , x);
    }
    for(int i = 1;i <= m;i++)
    {
        int l = read() , r = read();
        cout << b[ask(id[l - 1] , id[r] , 1 , q , (r - l + 1) / 2)] << endl;
    }
    return 0;
}

动态 dp

前置

这应该算一个神仙算法了吧，至少我<-这个蒟蒻学完是觉得这样的。

首现，你得会这些东西。

矩阵乘法，树链剖分，矩阵乘法优化dp。

是不是有一种心态碎成渣渣的欲望。

模板题：

P4719 【模板】"动态 DP"&动态树分治

对于LCT的做法，我太弱了，不会LCT，所以可以去看别的文章。

思路

dp部分

首先，我们可以考虑怎么暴力做这道题目。

矩阵乘法+dp！！！

我们尝试来推一下这个式子：

我们设 $f_{i , 1}$ 为选择 $i$，$i$ 的子树的最大权独立集的权值大小。

$f_{i , 0}$ 为不选择 $i$，$i$ 的子树的最大权独立集的权值大小。

则有一个清晰易懂的式子：

\[f_{i , 0} = \sum_{son=1}\max(f_{son,0},f_{son,1}) \]

\[f_{i , 1} = \sum_{son=1}f_{son,0}+a_i \]

最后的答案就是 $\max(f_{1, 0}, f_{1, 1})$。

然后，我们发现，这个东西带修以后，如果直接去跑，复杂度当场炸掉，有没有什么更快的方法呢。

这个时候，就需要引出我们的树链剖分了。

树链剖分部分

如果使用树链剖分，我们可以在 $O(\log(n)^2)$ 的复杂度下，实现单点修改。

这个复杂度和普通的树链剖分是一样的。

至于复杂度的证明。

我们可一从dp本身的角度考虑。

由于dp最主要的一点就是无后效性，所以它其实和直接的用数据结构维护区间和差不多。

我们现在只需要考虑如何在线段树里$O(1)$的修改和查询。

矩阵部分

你可以看到，题解区对于这一块的详细讲解非常少，对于我这种对矩阵乘法不太熟的萌新非常不友好。

所以我在这里会详细的说明矩阵部分。

~~以便我自己理解(狗头)~~

我们刚刚讲到。

需要考虑如何在线段树里 $O(1)$ 的修改和查询。

我们发现，可以用矩阵乘法进行优化。

$g_{i,1}$ 表示 $i$ 号点的所有轻儿子，都不取的最大权独立集；$g_{i, 0}$ 表示 $i$ 号点的所有轻儿子，可取可不取形成的最大权独立集。

那么刚刚那个式子就被简化成了：

\[f_{i,0} = \max(f_{j , 0}+g_{i,0},f_{j,1}+g_{i,0}) \]

\[f_{i,1} = \max(g_{i,1}+f_{j,0},-\infty) \]

这里参考了题解区题解。

我们可以考虑重定义区间乘法。

即：

mat operator *(const mat &tmp) const
{
    mat res; res.init();
    for(int i = 0;i <= 1;i++)
        for(int j = 0;j <= 1;j++)
            for(int k = 0;k <= 1;k++)
                res.a[i][j] = max(res.a[i][j] , a[i][k] + tmp.a[k][j]);
    return res;
}

至于矩阵的推导式子：

\[\begin{vmatrix}f_{p,0}&f_{p,0}\\f_{p,1}&-\infty\end{vmatrix} = \begin{vmatrix}f_{l,0}&f_{l,0}\\f_{l,1}&-\infty\end{vmatrix} * \begin{vmatrix}f_{r,0}&f_{r,0}\\f_{r,1}&-\infty\end{vmatrix} \]

其中，$p$ 为当前节点，$l$ 为左子节点 $r$ 为右子节点。

在建树的时候，将矩阵初始化为：

\[\begin{vmatrix}f_{i,0}&f_{i,0}\\f_{i,1}&-\infty\end{vmatrix} \]

然后直接用矩阵乘法进行 $O(1)$ 转移。

当然，在树剖往上跳的过程中，重链头部的矩阵同样需要转移。

我们设两个转移矩阵为：

\[\begin{vmatrix}a_{1}&b_{1}\\c_{1}&d_{1}\end{vmatrix} \]

\[\begin{vmatrix}a_{2}&b_{2}\\c_{2}&d_{2}\end{vmatrix} \]

要被转移的矩阵为：

\[\begin{vmatrix}x&y\\z&u\end{vmatrix} \]

那么转移方程为：

\[\begin{vmatrix}x&y\\z&u\end{vmatrix} = \begin{vmatrix}x+\max(a_{2},c_{1})-\max(a_{1},c_{1})&x+\max(a_{2},c_{1})-\max(a_{1},c_{1})\\z+a_{2}-a_{1}&u\end{vmatrix}\]

至于为什么是两个转移矩阵，我会在代码部分说明。

这样，我们就成功的完成了 $O(1)$ 的推导了(建议自己手推一下前两个)。

代码实现

代码实现比较难，我刷了整整一版提交记录，才卡了过去。

代码长达4.5KB（码风问题）。

细节看注释吧。

#include <bits/stdc++.h>
using namespace std;
const int inf = 99999999;
const int manx = 1e5 + 5;
int n , m , cnt , tot , a[manx] , nv[manx];
int dp[manx][3] , f[manx][3] ,  head[manx];
//dp数组

struct edge
{
    int to , nxt;
}e[manx * 2];
//连边

struct tree
{
    int siz , id , fa , top , son , dep , end;
}t[manx];
//树链剖分节点信息，注意这里需要多统计一个end，表示重链的尾巴。

struct ST
{
    int l , r;
    #define l(x) st[x].l
    #define r(x) st[x].r
    #define lp p * 2
    #define rp p * 2 + 1
}st[manx * 4];
//线段树

struct mat
{
    int a[3][3];
    void init()
    {
        for(int i = 0;i <= 1;i++)
            for(int j = 0;j <= 1;j++)
                a[i][j] = -inf;
    }
    mat operator *(const mat &tmp) const
    {
        mat res; res.init();
        for(int i = 0;i <= 1;i++)
            for(int j = 0;j <= 1;j++)
                for(int k = 0;k <= 1;k++)
                    res.a[i][j] = max(res.a[i][j] , a[i][k] + tmp.a[k][j]);
        return res;
    }
    //重定义的乘法
}ans, tr[manx * 4] , v[manx];
//矩阵
//tr为线段树中的矩阵，v[i]为编号为i的节点的矩阵。

int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

void add(int x , int y)
{
    e[++cnt] = (edge){y , head[x]} , head[x] = cnt;
    e[++cnt] = (edge){x , head[y]} , head[y] = cnt;
}

//TODO begin

void dfs1(int now , int com)
{
    t[now].siz = 1 , t[now].dep = t[com].dep + 1 , t[now].fa = com;
    int h = 0 , son = 0;
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == com) continue;
        dfs1(e[i].to , now);
        if(t[e[i].to].siz > h) h = t[e[i].to].siz , son = e[i].to;
        t[now].siz += t[e[i].to].siz;
    }
    t[now].son = son;
}
//树链剖分第一次dfs

void dfs2(int now , int gf)
{
    // cout << now << endl;
    t[now].id = ++tot; nv[tot] = now;
    t[gf].end = tot , t[now].top = gf;
    if(t[now].son) dfs2(t[now].son , gf);
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == t[now].fa || e[i].to == t[now].son)
            continue;
        dfs2(e[i].to , e[i].to);
    }
}
//树链剖分第二次dfs，注意要统计end。

void dfs3(int now)
{
    f[now][1] = a[now];
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == t[now].fa || e[i].to == t[now].son) continue;
        dfs3(e[i].to); 
        f[now][0] += max(dp[e[i].to][1] , dp[e[i].to][0]);
        f[now][1] += dp[e[i].to][0];
    }
    dp[now][0] += f[now][0] , dp[now][1] += f[now][1];
    if(!t[now].son) return;
    dfs3(t[now].son);
    dp[now][0] += max(dp[t[now].son][1] , dp[t[now].son][0]);
    dp[now][1] += dp[t[now].son][0];
}
//初始的答案计算。

//TODO seg_Tree

void build(int p , int l , int r)
{
    l(p) = l , r(p) = r;
    if(l == r)
    {
        // cout << p << " " << l << " " << r << " " << nv[l] << endl;
        v[nv[l]].a[0][0] = f[nv[l]][0] , v[nv[l]].a[1][0] = f[nv[l]][1];
        v[nv[l]].a[0][1] = f[nv[l]][0] , v[nv[l]].a[1][1] = -inf;
        //此处为第二个矩阵乘法推导式。
        tr[p] = v[nv[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(lp , l , mid) , build(rp , mid + 1 , r);
    tr[p] = tr[lp] * tr[rp];
    //此处为第一个推导式。
}
//建树

mat ask(int p , int l , int r)
{
    if(l <= l(p) && r(p) <= r) return tr[p];
    int mid = (l(p) + r(p)) >> 1;
    if(mid >= r) return ask(lp , l , r);
    if(mid < l) return ask(rp , l , r);
    // cout << p << " " << l << " " << r << endl;
    return ask(lp , l , r) * ask(rp , l , r);
    //同样的第一个推导式。
}

void update(int p , int id)
{
    if(l(p) == r(p))
    {
        // cout << p << " " << nv[id] << endl;
        tr[p] = v[nv[id]];
        //直接赋值就可以了。
        return;
    }
    int mid = (l(p) + r(p)) >> 1;
    if(mid >= id) update(lp , id);
    else update(rp , id);
    tr[p] = tr[lp] * tr[rp];
    //同样的。
}

void change(int u , int w)
{
    v[u].a[1][0] += w - a[u] , a[u] = w;
    //修改当前矩阵。
    while(u != 0)
    {
        mat x , y;
        int now = t[u].top;
        x = ask(1 , t[now].id , t[now].end);
        //修改前查询。
        update(1 , t[u].id);
        //将当前矩阵的修改转移到线段树上去。
        y = ask(1 , t[now].id , t[now].end);
        ///修改后查询。
        u = t[now].fa;
        //往上跳。
        // cout << u << " " << v[u].a[1][0] << " " << v[u].a[0][0] << endl;
        v[u].a[0][0] += max(y.a[0][0] , y.a[1][0]) - max(x.a[0][0], x.a[1][0] );
        v[u].a[0][1] = v[u].a[0][0];
        v[u].a[1][0] += y.a[0][0] - x.a[0][0];
        //第三个矩阵推导式，读者自行理解（可怜孩子并不会）。
    }
}
//树链剖分往上跳。

int main()
{
    n = read() , m = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i < n;i++)
    {
        int x = read() , y = read();
        add(x , y);
    }
    dfs1(1 , 0) , dfs2(1 , 1) , dfs3(1) , build(1 , 1 , n);
    for(int i = 1;i <= m;i++)
    {
        int x = read() , y = read();
        change(x , y);
        ans = ask(1 , t[1].id , t[1].end);
        // cout << ans.a[0][0] << " " << ans.a[1][0] << endl;
        cout << max(ans.a[0][0] , ans.a[1][0]) << endl;
        //max中两个分别对应暴力算法中的f[1][1]和f[1][0]。
    }
    return 0;
}

感受到算法的难度了吗，反正我感受到了。

一道例题

P5024 [NOIP2018 提高组] 保卫王国

有没有觉得现在看这道题感觉很简单。

因为最小权覆盖集 = 全集 - 最大权独立集。

所以直接修改查询就可以了。

当城市 $a$ 不得驻扎军队时。

将 $a$ 增加 $\infty$。

当城市 $a$ 必须驻扎军队时。

将 $a$ 减少 $\infty$。

如果查询的答案为 $\infty$。

则为无解。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 9999999999;
const int manx = 1e5 + 5;
int n , m , num , cnt , tot , a[manx] , nv[manx];
int dp[manx][3] , f[manx][3] ,  head[manx];
string type;

struct edge
{
    int to , nxt;
}e[manx * 2];

struct tree
{
    int siz , id , fa , top , son , dep , end;
}t[manx];

struct ST
{
    int l , r;
    #define l(x) st[x].l
    #define r(x) st[x].r
    #define lp p * 2
    #define rp p * 2 + 1
}st[manx * 4];

struct mat
{
    int a[3][3];
    void init()
    {
        for(int i = 0;i <= 1;i++)
            for(int j = 0;j <= 1;j++)
                a[i][j] = -inf;
    }
    mat operator *(const mat &tmp) const
    {
        mat res; res.init();
        for(int i = 0;i <= 1;i++)
            for(int j = 0;j <= 1;j++)
                for(int k = 0;k <= 1;k++)
                    res.a[i][j] = max(res.a[i][j] , a[i][k] + tmp.a[k][j]);
        return res;
    }
}ans, tr[manx * 4] , v[manx];

inline int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}

inline void add(int x , int y)
{
    e[++cnt] = (edge){y , head[x]} , head[x] = cnt;
    e[++cnt] = (edge){x , head[y]} , head[y] = cnt;
}

//TODO begin

inline void dfs1(int now , int com)
{
    t[now].siz = 1 , t[now].dep = t[com].dep + 1 , t[now].fa = com;
    int h = 0 , son = 0;
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == com) continue;
        dfs1(e[i].to , now);
        if(t[e[i].to].siz > h) h = t[e[i].to].siz , son = e[i].to;
        t[now].siz += t[e[i].to].siz;
    }
    t[now].son = son;
}

inline void dfs2(int now , int gf)
{
    // cout << now << endl;
    t[now].id = ++tot; nv[tot] = now;
    t[gf].end = tot , t[now].top = gf;
    if(t[now].son) dfs2(t[now].son , gf);
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == t[now].fa || e[i].to == t[now].son)
            continue;
        dfs2(e[i].to , e[i].to);
    }
}

inline void dfs3(int now)
{
    f[now][1] = a[now];
    for(int i = head[now];i;i = e[i].nxt)
    {
        if(e[i].to == t[now].fa || e[i].to == t[now].son) continue;
        dfs3(e[i].to); 
        f[now][0] += max(dp[e[i].to][1] , dp[e[i].to][0]);
        f[now][1] += dp[e[i].to][0];
    }
    dp[now][0] += f[now][0] , dp[now][1] += f[now][1];
    if(!t[now].son) return;
    dfs3(t[now].son);
    dp[now][0] += max(dp[t[now].son][1] , dp[t[now].son][0]);
    dp[now][1] += dp[t[now].son][0];
}

//TODO seg_Tree

inline void build(int p , int l , int r)
{
    l(p) = l , r(p) = r;
    if(l == r)
    {
        // cout << p << " " << l << " " << r << " " << nv[l] << endl;
        v[nv[l]].a[0][0] = f[nv[l]][0] , v[nv[l]].a[1][0] = f[nv[l]][1];
        v[nv[l]].a[0][1] = f[nv[l]][0] , v[nv[l]].a[1][1] = -inf;
        tr[p] = v[nv[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(lp , l , mid) , build(rp , mid + 1 , r);
    tr[p] = tr[lp] * tr[rp];
}

inline mat ask(int p , int l , int r)
{
    if(l <= l(p) && r(p) <= r) return tr[p];
    int mid = (l(p) + r(p)) >> 1;
    if(mid >= r) return ask(lp , l , r);
    if(mid < l) return ask(rp , l , r);
    // cout << p << " " << l << " " << r << endl;
    return ask(lp , l , r) * ask(rp , l , r);
}

inline void update(int p , int id)
{
    if(l(p) == r(p))
    {
        // cout << p << " " << nv[id] << endl;
        tr[p] = v[nv[id]];
        return;
    }
    int mid = (l(p) + r(p)) >> 1;
    if(mid >= id) update(lp , id);
    else update(rp , id);
    tr[p] = tr[lp] * tr[rp];
}

inline void change(int u , int w)
{
    v[u].a[1][0] += w , a[u] += w;
    while(u != 0)
    {
        mat x , y;
        int now = t[u].top;
        x = ask(1 , t[now].id , t[now].end);
        update(1 , t[u].id);
        y = ask(1 , t[now].id , t[now].end);
        u = t[now].fa;
        // cout << u << " " << v[u].a[1][0] << " " << v[u].a[0][0] << endl;
        v[u].a[0][0] += max(y.a[0][0] , y.a[1][0]) - max(x.a[0][0], x.a[1][0] );
        v[u].a[0][1] = v[u].a[0][0];
        v[u].a[1][0] += y.a[0][0] - x.a[0][0];
    }
}

signed main()
{
    n = read() , m = read(); cin >> type; 
    for(int i = 1;i <= n;i++) a[i] = read() , num += a[i];
    for(int i = 1;i < n;i++)
    {
        int x = read() , y = read();
        add(x , y);
    }
    dfs1(1 , 0) , dfs2(1 , 1) , dfs3(1) , build(1 , 1 , n);
    for(int i = 1;i <= m;i++)
    {
        int x1 = read() , y1 = read() , x2 = read() , y2 = read() , sum = 0;
        change(x1 , (y1 ? -inf : inf));
        change(x2 , (y2 ? -inf : inf));
        sum = ((y1 ^ 1) + (y2 ^ 1)) * inf;
        ans = ask(1 , t[1].id , t[1].end);
        sum = max(ans.a[0][0] , ans.a[1][0]) - sum;
        change(x1 , (y1 ? inf : -inf));
        change(x2 , (y2 ? inf : -inf));
        if(num - sum > inf) cout << -1 << endl;
        else cout << num - sum << endl;
    }
    return 0;
}

码农公寓

树状数组

一些拓展的小知识

树状数组套主席树

0. 一些基础的概念

1. 初始化

2. 读入

3. 离散化

4. 修改

5. 五个操作前的二分

6. 求区间第K大

7. 求区间K的排名

8. 求区间前驱后继

权值线段树

大致思路

Code

主席树

大致思路

0. 初始化

1. 建树

2. 单点修改

3. 区间查询

Code

Code

动态 dp

前置

思路

dp部分

树链剖分部分

矩阵部分

代码实现

一道例题

Code

相关文章