计算频率的线段树

Question

有没有什么方法可以使用线段树结构来计算数组中给定值的频率？

假设有一个大小为N的数组A，数组中每个元素A[i]的值为0、1或2。我要执行以下操作：

计算数组任意范围 [a,b] 中零的数量
递增(mod 3) 数组任意范围[a,b]内的每个元素

示例：如果 A = [0,1,0,2,0]:

Query[2,4] 必须 return 1 ，因为 [2,4]
Increment[2,4] 将 A 更新为 [0,2,1,0,0]

这看起来非常类似于范围求和查询问题，它可以使用线段树解决（在本例中由于范围更新而使用惰性传播），但我没有成功调整我的线段树代码来解决这个问题，因为如果我像在普通 RSQ 中一样将值存储在树中，则任何包含值“3”（例如）的父节点都没有任何意义，因为有了这些信息我无法提取其中存在多少零这个范围。

提前致谢！

--

编辑：

线段树是二叉树结构，在其节点中存储与数组相关的区间。叶节点存储实际的数组单元格，每个父节点存储其子节点的函数 f(node->left, node->right)。线段树通常用于执行范围求和查询，其中我们要计算数组范围 [a,b] 中所有元素的总和。在这种情况下，父节点计算的函数是其子节点中值的总和。我们想使用 segtrees 来解决范围和查询问题，因为它允许在 O(log n) 中解决它（我们只需要下降树直到找到范围查询完全覆盖的节点），比朴素的 O(n) 算法。

Answer 1

由于实际的数组值存储在叶子（级别 L）中，让级别 L - 1 的节点存储它们包含多少个零（这将是 [0, 2] 范围内的值）。除此之外，一切都是一样的，其余节点将 f(node->left, node->right) 计算为 node->left + node->right 并且零的计数将传播到根。

递增范围后，如果该范围不包含零，则无需执行任何操作。但是，如果该范围有零，那么所有这些零现在都将变为一，并且当前节点（称为 F）的函数值现在变为零。现在需要将值的变化向上传播到根，每次从函数值中减去 F。

Answer 2

使用平方根分解可以很容易地解决这道题首先创建新的前缀和数组，每个前缀和以 3 为模。将整个数组分成 sqrt(n) 个块。每个块都有 0、1 和 2 的数量。同时创建一个临时数组，其中包含要添加到块元素的总和这是 C++ 中的实现：

#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d",&a)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define pi(a) printf("%d\n",a)
#define pl(a) printf("%ld\n",a)
#define pll(a) printf("%lld\n",a) 
#define sc(a) scanf("%c",&a)
#define pc(a) printf("%c",a)
#define ll long long
#define mod 1000000007
#define w while
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF INT_MAX
#define fr(i,a,b) for(int i=a;i<=b;i++)



///////////////////////////////////////////////////////////////
struct block
{
    int one;
    int two;
    int zero;
    block()
    {
        one=two=zero=0;
    }
};
ll a[100005],a1[100005];
ll sum[400];
int main()
{
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    int N=(int)(sqrt(n));
    struct block b[N+10];
    for(int i=0;i<n;i++)
    {
        a[i]=s[i]-'0';
        a[i]%=3;
        a1[i]=a[i];
    }
    for(int i=1;i<n;i++)
    a[i]=(a[i]+a[i-1])%3;
    for(int i=0;i<n;i++)
    {
        if(a[i]==0)
        b[i/N].zero++;
        else if(a[i]==1)
        b[i/N].one++;
        else
        b[i/N].two++;
    }
    w(m--)
    {
        int type;
        si(type);
        if(type==1)
        {
            int ind,x;
            si(ind);
            si(x);
            x%=3;
            ind--;
                int diff=(x-a1[ind]+3)%3;
                if(diff==1)
                {
                    int st=ind/N;
                    int end=(n-1)/N;
                    int kl=(st+1)*N;
                    int hj=min(n,kl);
                    for(int i=st*N;i<hj;i++)
                    {
                        a[i]=(a[i]+sum[st])%3;
                    }
                    sum[st]=0;
                    for(int i=ind;i<hj;i++)
                    {
                        if(a[i]==0)
                        b[st].zero--;
                        else if(a[i]==1)
                        b[st].one--;
                        else
                        b[st].two--;


                        a[i]=(a[i]+diff)%3;



                        if(a[i]==0)
                        b[st].zero++;
                        else if(a[i]==1)
                        b[st].one++;
                        else
                        b[st].two++;
                    }

                    for(int i=st+1;i<=end;i++)
                    {
                        int yu=b[i].zero;
                        b[i].zero=b[i].two;
                        b[i].two=b[i].one;
                        b[i].one=yu;
                        sum[i]=(sum[i]+diff)%3;
                    }
                }
                else if(diff==2)
                {


                    int st=ind/N;
                    int end=(n-1)/N;
                    int kl=(st+1)*N;
                    int hj=min(n,kl);
                    for(int i=st*N;i<hj;i++)
                    {
                        a[i]=(a[i]+sum[st])%3;
                    }
                    sum[st]=0;
                    for(int i=ind;i<hj;i++)
                    {
                        if(a[i]==0)
                        b[st].zero--;
                        else if(a[i]==1)
                        b[st].one--;
                        else
                        b[st].two--;


                        a[i]=(a[i]+diff)%3;



                        if(a[i]==0)
                        b[st].zero++;
                        else if(a[i]==1)
                        b[st].one++;
                        else
                        b[st].two++;
                    }

                    for(int i=st+1;i<=end;i++)
                    {
                        int yu=b[i].zero;
                        b[i].zero=b[i].one;
                        b[i].one=b[i].two;
                        b[i].two=yu;
                        sum[i]=(sum[i]+diff)%3;
                    }
                }

            a1[ind]=x%3;
        }
        else
        {
            int l,r;
            ll x=0,y=0,z=0;
            si(l);
            si(r);
            l--;
            r--;
            int st=l/N;
            int end=r/N;
            if(st==end)
            {
                for(int i=l;i<=r;i++)
                {
                    ll op=(a[i]+sum[i/N])%3;
                    if(op==0)
                    x++;
                    else if(op==1)
                    y++;
                    else 
                    z++;
                }
            }
            else
            {
                for(int i=l;i<(st+1)*N;i++)
                {
                    ll op=(a[i]+sum[i/N])%3;
                    if(op==0)
                    x++;
                    else if(op==1)
                    y++;
                    else 
                    z++;
                }
                for(int i=end*N;i<=r;i++)
                {
                    ll op=(a[i]+sum[i/N])%3;
                    if(op==0)
                    x++;
                    else if(op==1)
                    y++;
                    else 
                    z++;
                }
                for(int i=st+1;i<=end-1;i++)
                {
                    x+=b[i].zero;
                    y+=b[i].one;
                    z+=b[i].two;
                }
            }
            ll temp=0;
            if(l!=0)
            {
                temp=(a[l-1]+sum[(l-1)/N])%3;
            }
            ll ans=(x*(x-1))/2;
            ans+=((y*(y-1))/2);
            ans+=((z*(z-1))/2);
            if(temp==0)
            ans+=x;
            else if(temp==1)
            ans+=y;
            else
            ans+=z;
            pll(ans);
        }
    }
    return 0;
}

计算频率的线段树

Segment Tree to compute frequencies

arrays

data-structures

segment-tree