前缀查询（字典树+线段树懒惰标记）

89 阅读 0 评论 59 点赞

我是靠谱客的博主飞快星月，最近开发中收集的这篇文章主要介绍前缀查询（字典树+线段树懒惰标记），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

描述
在一个 Minecraft 村庄中，村长有这一本小写字母构成的名册（字符串的表），
每个名字旁边都记录着这位村民的声望值，而且有的村民还和别人同名。
随着时间的推移，因为没有村民死亡，这个名册变得十分大。
现在需要您来帮忙维护这个名册，支持下列 4 种操作：
1. 插入新人名 si，声望为 ai
2. 给定名字前缀 pi 的所有人的声望值变化 di
3. 查询名字为 sj 村民们的声望值的和（因为会有重名的）
4. 查询名字前缀为 pj 的声望值的和
输入描述:
第一行为两个整数 0 ≤ N ≤ 105，表示接下来有 N 个操作；
接下来 N 行，每行输入一个操作，行首为一个整数 1 ≤ oi ≤ 4，表示这一行的操作的种类，
那么这一行的操作和格式为：
1. 插入人名，这一行的格式为 1 si ai，其中 |ai| ≤ 103
2. 前缀修改声望，这一行的格式为 2 pi di，其中 |di| ≤ 103
3. 查询名字的声望和，这一行的格式为 3 sj
4. 查询前缀的声望和，这一行的格式为 4 pj
输入保证插入人名的字符串的长度和小于或等于 105，总的字符串的长度和小于或等于 106。
输出描述:
对于每一次询问操作，在一行里面输出答案。
示例1
输入
20
1 a -10
1 abcba -9
1 abcbacd 5
4 a
2 a 9
3 aadaa
3 abcbacd
4 a
3 a
2 a 10
3 a
2 a -2
2 d -8
1 ab -2
2 ab -7
1 aadaa -3
4 a
3 abcba
4 a
4 c
输出
-14
0
14
13
-1
9
11
1
11
0

思路：

看到这个，很明显的字典树，但是有一个前缀修改，这个只用字典树实现不了，但是应用了线段树的懒惰标记就可以了。

调试了好久，经过不懈努力，终于把这道题给补上了。

代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=110000;
struct Node
{
    LL sum,va;
    int qian,same;
    LL d;
    int ch[30];
}G[maxn];
int ans,root;
inline int idx(char x)
{
    return x-'a';
}
void pushdown(int u)
{
    if(u&&G[u].d)
    {
        for(int i=0;i<26;i++)
        {
            if(G[u].ch[i])continue;
            G[G[u].ch[i]].d+=G[u].d;
            G[G[u].ch[i]].sum+=G[G[u].ch[i]].qian*G[u].d;
            G[G[u].ch[i]].va+=G[G[u].ch[i]].same*G[u].d;
        }
        G[u].d=0;
    }
}
void inset(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])
        {
            G[u].ch[v]=++ans;
        }
        G[u].qian++;
        G[u].sum+=val;
        u=G[u].ch[v];
        pushdown(u);
    }
    G[u].qian++;
    G[u].sum+=val;
    G[u].same++;
    G[u].va+=val;
}

void update(char *a,int val)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        u=G[u].ch[v];
    }
    int qian=G[u].qian;
    u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return;
        G[u].sum+=qian*val;
        u=G[u].ch[v];
        pushdown(u);
    }

    G[u].sum+=qian*val;
    G[u].va+=G[u].same*val;
    G[u].d+=val;
}
LL select1(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].va;
}
LL select2(char *a)
{
    int l=strlen(a);
    int u=root;
    for(int i=0;i<l;i++)
    {
        int v=idx(a[i]);
        if(!G[u].ch[v])return 0;
        u=G[u].ch[v];
        pushdown(u);
    }
    return G[u].sum;
}
char b[maxn];
int t,k,w;
int main()
{
    ans=1;
    root=1;
    memset(G,0,sizeof(G));
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%s %d",b,&w);
            inset(b,w);
        }
        else if(k==2)
        {
            scanf("%s %d",b,&w);
            update(b,w);
        }
        else if(k==3)
        {
            scanf("%s",b);
            printf("%lldn",select1(b));
        }
        else if(k==4)
        {
            scanf("%s",b);
            printf("%lldn",select2(b));
        }
    }
    return 0;
}