遅延セグメントツリーをC#で動かす

先日のEducational Codeforces Contest でE問題が遅延セグメントツリーを利用する必要があったのですがpypyでは通らなかったのでC#で書き直してACを得ました。 せっかくなので実装を残しておきます。 非再帰版の遅延評価セグメント木の実装メモ - 日々ｄｒｄｒする人のメモ の書き方が簡潔だったのでほぼ丸写しです。

using System;
using System.Linq;
using System.Collections.Generic
using static System.Math;

class SegTree
{
  public long[] data;
  public long[] lazydata;
  private int num;
  private long ide_ele;
  private long F(long x, long y){
    if (x>y) return x;
    return y;
  }
  private int Pow(int x, int y){
    int r = 1;
    for (int i = 0; i < y; i++){
      r *= x;
    }
    return r;
  }
  private List<int> Gindices(int l, int r){
    List<int> R = new List<int>();
    l += num; r += num;
    int lm = (l / (l & -l))>>1;
    int rm = (r / (r & -r))>>1;
    //Console.WriteLine(rm);
    while (l < r){
      if (r <= rm){
        R.Add(r-1);
      }
      if (l <= lm){
        R.Add(l-1);
      }
      l >>= 1; r >>= 1;
    }
    while (l > 0){
      R.Add(l-1);
      l >>= 1;
    }
    return R;
  }

  private void Propagate(List<int> indices){
    foreach(int i in indices.AsEnumerable().Reverse()){
      long v = lazydata[i]; lazydata[i] = 0;
      if (v==0) continue;
      lazydata[2*i+1] += v; data[2*i+1] += v;
      lazydata[2*i+2] += v; data[2*i+2] += v;
    }
  }

  public void Update(int i, long x){
    i += num-1;
    data[i] = x;
    while (i>0){
      i = (i-1)>>1;
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
  public void UpdateRange(int l, int r, long x){
    //Console.WriteLine($"{l}, {r}");
    List<int> gindices = Gindices(l, r);
    l += num; r += num;
    while (l < r){
      if (l%2 == 1){
        lazydata[l-1] += x; data[l-1] += x; l++;
      }
      if (r%2 == 1){
        r--; lazydata[r-1] += x; data[r-1] += x;
      }
      l >>= 1; r >>= 1;
    }
    foreach(int i in gindices){
      //Console.WriteLine(i);
      data[i] = F(data[2*i+1], data[2*i+2]) + lazydata[i];
    }
  }
  public long Query(int l, int r){
    Propagate(Gindices(l, r));
    l += num; r += num;
    long R = ide_ele;
    while (l < r){
      //Console.WriteLine($"Q {l-1} {r-2}");
      if (l%2 == 1){
        R = F(R, data[l-1]); l++;
      }
      if (r%2 == 1){
        r--; R = F(R, data[r-1]);
      }
      l >>= 1; r >>= 1;
    }
    return R;
  }
  public SegTree(long[] values, long ide_ele)
  {
    int N = values.Length;
    this.ide_ele = ide_ele;
    int tmp = N+1; // 遅延操作のため1段多く作る
    int r = 0;
    while (tmp > 0){
      tmp >>= 1;
      r++;
    }
    num = Pow(2, r);
    data = new long[2*num];
    lazydata = new long[2*num];
    for (int i = 0; i < N; i++){
      data[i+num-1] = values[i];
    }
    for (int i = num - 2; i >= 0; i--){
      data[i] = F(data[2*i+1], data[2*i+2]);
    }
  }
}

class P
{
  static void Main()
  {
    SegTree x = new SegTree(new long[] {12, 32, 21, 24}, -long.MaxValue);
    x.Update(0, 53);
    x.UpdateRange(2, 3, 8);
    x.UpdateRange(2, 4, 5);
    Console.WriteLine(x.Query(1, 4));
  }
}

利用例 :

https://codeforces.com/contest/1295/submission/69992196

問題は抽象化で現在、各値はlongで持つことが前提の実装になっています。 色々な型を入れられるようになりたいな。C#の習熟度が足りないのでまた次回に。