Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
using static System.Console;
using static System.Linq.Enumerable;
using CompetitiveCSharp;
namespace CSharpTest
{
static class Program
{
static void WriteTree(SegTree tree)
{
for(var i = 0; i < tree.Length; ++i)
{
for(var j = 0; j <= tree.Length; ++j)
{
Write($"{tree.Get(i, j)} ");
}
WriteLine();
}
}
static void Main(string[] args)
{
var test = new int[8];
foreach(var i in Range(0, 8))
{
test[i] = i + 1;
}
var tree = new SegTree(test, (a, b) => a + b);
WriteTree(tree);
WriteLine();
tree[1] = 9;
tree[3] = 10;
tree[5] = 11;
tree[7] = 12;
WriteTree(tree);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Linq.Enumerable;
namespace CompetitiveCSharp
{
static class SegTreeHelp
{
const int check_count = 1000000;
public static int GetUnit(this Func<int, int, int> op)
{
var random = new Random();
var kouho = new int[] { 0, 1, int.MinValue, int.MaxValue };
foreach (var u in kouho)
{
var f = true;
foreach (var c in Range(0, check_count))
{
var v = random.Next();
if (v != op(v, u) || v != op(u, v))
{
f = false;
break;
}
}
if (f)
{
return u;
}
}
throw new ArgumentException("与えられた関数は単位元を持ちません");
}
}
public class SegTree
{
int[] vec;
Func<int, int, int> op;
public int Length { get; }
int unit;
static int GetSize(int s)
{
if ((s & -s) == s)
{
return s;
}
while ((s & -s) != s)
{
s -= s & -s;
}
return s << 1;
}
public SegTree(int size, Func<int, int, int> op)
{
this.vec = new int[2 * GetSize(size)];
this.op = op;
this.unit = this.op.GetUnit();
this.Length = this.vec.Length / 2;
foreach(var i in Range(0, 2 * this.Length))
{
this.vec[i] = this.unit;
}
}
public SegTree(IEnumerable<int> init, Func<int, int, int> op) : this(init.Count(), op)
{
var i = this.Length;
foreach (var v in init)
{
this.vec[i++] = v;
}
foreach(var index in Range(1, this.Length - 1).Reverse())
{
this.vec[index] = op(this.vec[2 * index], this.vec[2 * index + 1]);
}
}
public int Get(int a, int b)
{
var L = this.unit;
var R = this.unit;
for (a += this.Length, b += this.Length; a < b; a >>= 1, b >>= 1)
{
if ((a & 1) != 0)
{
L = this.op(L, this.vec[a++]);
}
if ((b & 1) != 0)
{
R = this.op(this.vec[--b], R);
}
}
return this.op(L, R);
}
public int this[int index]
{
get
{
return this.vec[this.Length + index];
}
set
{
this.vec[this.Length + index] = value;
for(var s = (this.Length + index) / 2; s > 0; s /= 2)
{
this.vec[s] = this.op(this.vec[2 * s], this.vec[2 * s + 1]);
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment