智乃与无意义的题目——树状数组

题目描述

中心思想

线段树or树状数组
由于一些不可说的原因（菜），所以先写树状数组的解法。

初步分析

1、如何查询

求数n因数的个数，有公式f(n)=(2^k1 + 1)(3^k2 + 1)(5^k3 + 1)(7^k4 + 1)··· 其中，n=2^k1 * 3^k2 * 5^k3```
因此，对n先进行质因数分解，然后代入公式即可。而本题目中ai 10，故其质因数只有2,3,5,7四种情况。
举个栗子：
设ai =(2^k[i][1] + 1)(3^k[i][2] + 1)(5^k[i][3] + 1)(7^k[i][4] + 1) ,
则a1 * a2 * a3 * ···=[2^(k[1][1]+k[2][1]+k[3][1]+···）] * [3^(k[1][2]+k[2][2]+k[3][2]+···）] * [5^(k[1][3]+k[2][3]+k[3][3]+···）] * [7^(k[1][4]+k[2][4]+k[3][4]+···）]

2、如何求al到ar乘积的质因数分解个数

由于需要求k[l][j]~k[r][j]的序列和，且数组a可以通过操作1不断更新，因此考虑采用树状数组的方式存储。

题目思路

首先对数组进行定义：

//n为所输入的元素数，a[MAXN]保存输入的元素
int n,a[MAXN];
//factor[]保存可能出现的质因数
int factor[]={2,3,5,7};
//对于a[i],将其各质因数个数存入factor_num[i][5]中
ll factor_num[MAXN][5];
//以factor_num[i][5]为基础数组，建立树状数组factor_tree[10][i]
ll factor_tree[10][MAXN]={0};

【树状数组维护】

//求x二进制形式末尾0的个数
ll lowbit(ll x)
{
    return x&(-x);
}
//更新操作
void update(int x,int j,int tot,int c)//输入操作时c=1,更改操作时c=-1 
{
    while(j<=n)
    {
        factor_tree[x][j]+=(c*tot);
        j+=lowbit(j);//寻找下一个包含被更改元素的树节点 
    }
}
//通过对factor_tree[x][j]操作求factor_num[j][x]前缀和
ll getsum(int x,int j)
{
    ll ans=0;
    while(j>0)
    {
        ans=ans+factor_tree[x][j];
        j-=lowbit(j);//寻找下一个需要被加的树节点 
    }
    return ans; 
 }

这一部分代码是在基本的树状数组基础上改编的，可以参考以下两篇博客学习：
https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html
https://www.cnblogs.com/xenny/p/9739600.html
这两位大佬已经讲得十分详细了，这里不再赘述。
【主函数】

 int main()
 {
     int q;
     scanf("%d%d",&n,&q);
     //输入a[]数组
     for(int i=1;i<=n;i++)
     {
         scanf("%d",&a[i]);
        //输入a[i]时即对其进行质因数分解处理，利用update函数建立树状数组
         for(int j=0;j<4;j++)
         {
             ll tot=0;
             while(a[i]%factor[j]==0)
             {
                 tot++;
                 a[i]/=factor[j];
             }
             factor_num[i][j]=tot;
             update(factor[j],i,tot,1);
         }
     }
     //输入操作
     while(q--)
     {
         ll list,r,l;
         scanf("%lld%lld%lld",&list,&r,&l);
        //若是操作1，先从原树状数组中删去与被改变元素相关的部分，
        //再将与新加入的元素相关的部分加入树状数组
         if(list==1)
         {
             for(int i=0;i<4;i++)
             {
                 update(factor[i],r,factor_num[r][i],(-1));
            }
            for(int i=0;i<4;i++)
            {
                ll tot=0;
                while(l%factor[i]==0)
                {
                    tot++;
                    l/=factor[i];
                }
                factor_num[r][i]=tot;
                update(factor[i],r,tot,1);
            }
        }
        //若是操作2，直接根据公式求和输出
        else if(list==2)
        {
             ll ans=1;
             for(int i=0;i<4;i++)
             {
                 ans=(ans*(getsum(factor[i],l)-getsum(factor[i],r-1)+1))%MOD;
            }
             printf("%lld\n",ans);
        }
     }
     return 0;
 }

总结

树状数组是求前缀和的方法，它比线段树的实现更加简单。树状数组的重点在于理解其与基础数组的关系。我们可以理解为，树状数组的每一个节点是对几个基础数组节点的覆盖。本题目中，基础数组是factor_num[][],树状数组是factor_tree[][]。