あなたはどのワードでここに辿り着きましたか？
先にコードを載せます。超普通のセグ木になります。
using System;
using System.Collections.Generic;
using System.Linq;
namespace Library
{
public class SegmentTree<T> where T: struct
{
private readonly T[] data;
private int size = 1;
private T defaultValue;
private Func<T, T, T> function;
public SegmentTree(int size, T defaultValue, Func<T, T, T> function)
{
while(this.size < size) this.size *= 2;
this.defaultValue = defaultValue;
this.function = function;
data = Enumerable.Repeat(defaultValue, this.size * 2 - 1).ToArray();
}
// [a, b)
public T RangedValue(int a, int b) { return RangedValue(a, b, 0, 0, size); }
private T RangedValue(int a, int b, int now, int l, int r)
{
if (r <= a || b <= l) return defaultValue;
if (a <= l && r <= b) return data[now];
return function(RangedValue(a, b, now * 2 + 1, l, (l + r) / 2), RangedValue(a, b, now * 2 + 2, (l + r) / 2, r));
}
public T this[int index]
{
get
{
return data[size + index - 1];
}
set
{
index += size - 1;
data[index] = value;
while (index > 0)
{
index = (index - 1) / 2;
data[index] = function(data[index * 2 + 1], data[index * 2 + 2]);
}
}
}
}
}
以下工夫した点
- Genericsの型であるTに値型の制約を与えた
- indexによるアクセスでより直感的に
- ぐう短い
