【google】 google

Google mock view

前段时间做了一下google的mock interview,其中有道题目印象深刻。

1. 区间查询

题目

给定长度为n的数组A，给定组数$[i,j]$，求以下结果:

$$query(i,j) = \prod_{k=1}^{j-i+1}(A_{i+k-1}^{k})$$

所求结果对$10^{9} + 7$取模, 其中满足以下：

• $i \le j$
• $1 \le n \le 10^{5}$
• $0 \le A[i] \le 10^{9}$

  地址

  https://leetcode-cn.com/problems/truncate-sentence

  题意

  线段树

  解题思路

1. 首先看到类似的求区间的数列我们首先想到的就是用线段树。我们首先用数学分解的方法来将公式进行分解和变换： $$A[i,j] = \prod_{k=i}^{j}(A_{k}^{k-i+1}) \\ = \prod_{m=i}^{s-1}(A_{m}^{m+1-i}) * \prod_{n=s}^{j}(A_{n}^{n+1-i}) \\ = \prod_{m=i}^{s-1}(A_{m}^{m+1-i}) * \prod_{n=s}^{j}(A_{n}^{n+1-s})*(\prod_{n=s}^{j}A_{n})^{s-i} \\$$ 由上述变换我们就可以知道如何通过线段树对其进行分解，我们设线段树的每个非叶子节点，包含的范围为$(i,j)$,且包含两个值： $$prod_{(i,j)} = \prod_{k=i}^{j}A_{k}\\ val_{(i,j)} = \prod_{k=i}^{j}A_{k}^{k+1-i}\\$$ 有了上述变换以后我们可以知道线段树的变化，假如本次我们需要查询的区间为$(i,j)$,假设线段从$mid$处断开分为两个子节点，则我们可以知道如下的求和公式： $$prod_{(i,j)} = \prod_{k=i}^{j}A_{k} = \prod_{k=i}^{mid}A_{k}*\prod_{k=mid+1}^{j}A_{k} \\ = prod_{(i,mid)}*prod_{(mid+1,j)} \\$$ 而$val$可以变换如下： $$val_{(i,j)} = \prod_{k=i}^{j}A_{k}^{k+1-i} = \prod_{k=i}^{mid}(A_{k}^{k+1-i}) * \prod_{k=mid+1}^{j}(A_{k}^{k+1-i}) \\ = \prod_{k=i}^{mid}(A_{k}^{k+1-i}) * \prod_{k=mid+1}^{j}(A_{k}^{k+1-(mid+1)})*(\prod_{k=mid+1}^{j}A_{k})^{mid+1-i} \\ = val_{(i,mid)}*val_{(mid+1,j)}*(prod_{(mid+1,j)})^{mid+1-i}$$ 根据以上变换，我们则可以轻易的用线段树可以在$lg(n)$的时间复杂度内求出所有的查询。

   代码

   #include<bits/stdc++.h>
   
   using namespace std;
   
   typedef long long ll;
   typedef pair<int,int> pii;
   long long MOD = 1e9 + 7;
   const long long MAXN = 2000000;
   struct segTreeNode{
       long long val;
       long long prod;
       int l;
       int r;
   };
   
   #define CHL(x) (x*2)
   #define CHR(x) (x*2+1)
   segTreeNode tree[MAXN];
   
   long long fastpow(long long x,long long y,long long mod){
       long long ret = 1;
       for(int i = y; i != 0; i >>= 1){
           if(i&1) ret = (ret*x)%mod;
           x = (x*x)%mod;
       }
       return ret;
   }
   
   bool pushUpTree(int idx){
       int mid = (tree[idx].l + tree[idx].r)>>1;
       int d = mid - tree[idx].l + 1;
       long long pl = tree[CHL(idx)].prod;
       long long pr = tree[CHR(idx)].prod;
       tree[idx].prod = pl*pr%MOD;
       tree[idx].val = tree[CHL(idx)].val*tree[CHR(idx)].val*fastpow(pr,d,MOD)%MOD;
       return true;
   }
   
   bool buildTree(int l,int r,vector<int> & arr,int idx){
       if(l > r) return false;
       tree[idx].l = l;
       tree[idx].r = r;
       tree[idx].val = 1;
       tree[idx].prod = 1;
       if(l == r){
           tree[idx].val = arr[l];
           tree[idx].prod = arr[l];
           return true;
       }
   
       int mid = (l+r)>>1;
       buildTree(l,mid,arr,CHL(idx));
       buildTree(mid+1,r,arr,CHR(idx));
       pushUpTree(idx);
       return true;
   }
   
   long long queryTree(int l,int r,int idx){
       if(tree[idx].r < l || tree[idx].l > r) return 1;
       if(l <= tree[idx].l &&  tree[idx].r <= r){
           long long d = tree[idx].l - l;
           return tree[idx].val*fastpow(tree[idx].prod,d,MOD)%MOD;
       }
   
       int mid = (tree[idx].l + tree[idx].r)>>1;
       if(l > mid){
           return queryTree(l,r,CHR(idx));
       }else if(r <= mid){
           return queryTree(l,r,CHL(idx));
       }else{
           long long lval = queryTree(l,r,CHL(idx));
           long long rval = queryTree(l,r,CHR(idx));
           return lval*rval%MOD;
       }
   }
   
   int main(){
       int n;
       int t;
       int l,r;
       memset(tree,0,sizeof(tree));
       cin>>n;
       vector<int> arr = vector<int>(n);
       for(int i = 0; i < n; ++i) cin>>arr[i];
       buildTree(0,n-1,arr,1);
       cin>>t;
       for(int i = 0; i < t; ++i){
           cin>>l>>r;
           l--;
           r--;
           cout<<queryTree(l,r,1)<<endl;
       }
       return 0;
   }

#

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿