yukicoder No.2265 Xor Range Substring Sum Query の計算量解析

問題
#848556 のアルゴリズムの解説
結論
(A) の証明
(B) の証明
1. 実験による検証
おまけ

問題

No.2265 Xor Range Substring Sum Query - yukicoder

yukicoder No.2265 Xor Range Substring Sum Query の解説で別解として触れられている、提出 #848556 に示されるアルゴリズムの計算量は $n\leq 18$ で十分高速でしょうか？あるいは、どのようなオーダーで表されるでしょうか？

#848556 のアルゴリズムの解説

$Q_2(L,R,X)=f(S_{L\oplus X}S_{(L+1)\oplus X}\cdots S_{(R-1)\oplus X})$ ( $0\leq L\lt R\leq 2^n$ , $0\leq X\lt 2^n$ )
$\mathcal{Q}(p,d,X)=Q_2(p2^d,(p+1)2^d,X)$ ( $0\leq d\leq n$ , $0\leq p\lt 2^d$ , $0\leq X\lt 2^d$ )

とおきます。 $Q_2(L,R,X)$ はクエリごとに求める答えの計算式の $R$ を調整したものです。

ある $p_1,p_2,p_3,X$ ( $0\leq p_1\lt p_2\lt p_3\leq 2^n$ ) に対して $Q_2(p_1,p_2,X)$ と $Q_2(p_2,p_3,X)$ の値がわかっているとき、 $Q_2(p_1,p_3,X)$ の値を $O(1)$ 時間で計算できることがわかっています。これを利用すると、セグメントツリーの要領で必要な計算は $\mathcal{Q}(p,d,X)$ の値の取得に帰着します。

$\mathcal{Q}(p,d+1,X+a2^d)$ ( $a=0,1$ ) の値を要求されたタイミングで、 $\mathcal{Q}(2p,d,X)$ と $\mathcal{Q}(2p+1,d,X)$ を値を再帰的に要求します。

$\mathcal{Q}(p,d,X)$ を計算した場合、その値をメモに保存し、 $p2^d\leq x\lt (p+1)2^d$ に対して更新があるまでその値を使いまわします。これによって再帰のうちのいくらかは打ち切られるため、計算量が改善しそうに思われます。

$(p,d)$ ごとに最終更新時刻を記録しておき、これを $\mathcal{Q}(p,d,X)$ を最後に計算した時刻と比較することで更新を検知し、適切に再計算します。

結論

(A) クエリごとの計算量は、償却 $O(2^{n/2})$ 時間です。オーダーのみから判断する場合、解法としては十分高速でしょう。

(B) また、 $2^{n/2}\leq Q$ 程度に $Q$ が大きいとき、全体で $\Theta(Q2^{n/2})$ 時間かかるようなクエリの列が存在します。

(A) の証明

最終更新時刻の記録は簡単です。以降では $\mathcal{Q}(p,d,X)$ の計算を考えます。

$Q_2(L,R,X)$ を求めるクエリについて、 $L=0$ かつ $R=2^n$ のクエリすなわち数列全域を対象としたクエリのみ考えます。この場合のクエリは特定の $X$ についてすべての $\mathcal{Q}(p,d,X\bmod 2^d)$ の計算を要求し、実質的に他の組 $(L,R)$ の計算内容を包含しているため、このようなクエリのみとしても問題ありません。

$n$ は偶数として $d\lt n/2$ と $n/2\leq d$ に分けて考えます。 $n/2\leq d$ は再帰が浅い部分であり、値の要求が $O(2^{n/2})$ 回しかないので、主張に直接は関わりません。

$d\lt n/2$ の範囲でクエリ $1$ 回で破棄されるメモの個数を見積もります。 $(x,d)$ に対して $p$ は一意なので、特定の $d$ では最大 $2^d$ 箇所のメモが破棄されます。これを $d\lt n/2$ について足し上げても $2^{n/2}$ を超えません。この個数は今後 $d\lt n/2$ の範囲内で発生する計算の再帰 $1$ 回ごとに消費されるので、計算量は償却すれば $O(2^{n/2})$ 時間です。

(B) の証明

$n^{\prime}={\lfloor n/2\rfloor}$ とおき、 $2\leq n^{\prime}$ として $\Theta\left(2^{n^{\prime}}\right)$ 回のクエリで $\Theta(2^n)$ 時間かかるようにします。

$x=0\cdot 2^{n^{\prime}},1\cdot 2^{n^{\prime}},2\cdot 2^{n^{\prime}},\ldots ,2^n-2^{n^{\prime}}$ に対して更新したあと、
$X=0,1,2,\ldots ,2^{n^{\prime}}-1$ について $Q_2(0,2^n,X)$ の値を要求する

というクエリ列を考えます。クエリは $2^{n-n^{\prime}}+2^{n^{\prime}}$ 回です。

更新によって $d=n^{\prime}$ における $2^n$ 個のメモはすべて破棄されます。また、値の要求によって $d=n^{\prime}$ における計算はすべて $1$ 回ずつ要求されます。よって、アルゴリズムは $\Theta(2^n)$ 時間を消費します。

実験による検証

提出 #848556 の main 関数を次のプログラムに置き換えることで、プログラムは、 $n=12$ において上記クエリ列を実行する過程で $d=n^{\prime}$ におけるメモが無効化されている個数をクエリごとに数えて出力するようになります。出力も下に添えます。

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int ns = 6;
  n = ns * 2;
  N=1<<n;
  Time=1;

  pow11[0]=1;
  pow2[0]=1;
  for(int i=1;i<N;i++){
    pow11[i]=pow11[i-1]*11;
    pow2[i]=pow2[i-1]*2;
  }
  for(int i=0;i<2*N;i++){
    lazy[i]=0;
  }

  string s = string(N, '1');

  for(int i=0;i<N;i++){
    node[0][i]={s[i]-'0',1};
  }

  build();
  
  auto countReset = [&]() -> int {
    int ans = 0;
    for(int p=0; p<(N>>ns); p++) for(int x=0; x<(1<<ns); x++){
      if(last_update[ns][(p<<ns)+x] < lazy[(1<<ns)+p]) ans++;
    }
    return ans;
  };
  
  for(int x=0; x<N; x+=(1<<ns)){
    update(x,{1,1});
    cout << countReset() << " ";
  } cout << endl;
  for(int x=0; x<(1<<ns); x+=1){
    query(0,N,x);
    cout << countReset() << " ";
  } cout << endl;
  return 0;
}

64 128 192 256 320 384 448 512 576 640 704 768 832 896 960 1024 1088 1152 1216 1280 1344 1408 1472 1536 1600 1664 1728 1792 1856 1920 1984 2048 2112 2176 2240 2304 2368 2432 2496 2560 2624 2688 2752 2816 2880 2944 3008 3072 3136 3200 3264 3328 3392 3456 3520 3584 3648 3712 3776 3840 3904 3968 4032 4096 
4032 3968 3904 3840 3776 3712 3648 3584 3520 3456 3392 3328 3264 3200 3136 3072 3008 2944 2880 2816 2752 2688 2624 2560 2496 2432 2368 2304 2240 2176 2112 2048 1984 1920 1856 1792 1728 1664 1600 1536 1472 1408 1344 1280 1216 1152 1088 1024 960 896 832 768 704 640 576 512 448 384 320 256 192 128 64 0

おわり

おまけ

同じコンテストでの出題 No.2262 Fractions の制約拡大版である No.2266 Fractions (hard) に関してです。

Mertens 関数の計算のために計算量は $O(N^{2/3})$ 時間であるというほかありませんが、制約内では Mertens 関数の計算はかなり高速であり、 $\displaystyle\sum_{y=1}^NM\left(\left\lfloor \frac{N}{y}\right\rfloor\right)g(y)$ （式は解説から引用）の処理のほうが重要になっています。

$y$ の範囲をある値 $D$ の前後で分けて、

$y\leq D$ のとき、 $y$ を $1$ つごとに $O(1)$ 時間で処理する
$D\lt y$ のとき、 $\left\lfloor \frac{N}{y}\right\rfloor$ がとる値ごとに floor sum で一括で計算し、全体では $O\left(\dfrac{N}{D}\log N\right)$ 時間で処理する

ことで、全体で $O\left(D+\dfrac{N}{D}\log N\right)$ 時間になります。解説では $D\approx \sqrt{N}$ にとっていますが、計算量の最小化は $D\approx\sqrt{N\log N}$ で達成され、このときの計算量は $O(\sqrt{N\log N})$ です。（なお、 Stern-Brocot Tree 上の二分探索のために計算量はさらに $\log N$ 倍されます。）

おまけ　おわり