あなたはどのワードでここに辿り着きましたか？
先にコードを載せます。超普通のセグ木になります。
- 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によるアクセスでより直感的に
- ぐう短い
