class NgLib::DualSegTree(T)

Overview

区間作用・$1$ 点取得ができるセグメント木です。

作用素 $f$ は、要素 $x$ と同じ型である必要があります。

Included Modules

Defined in:

nglib/data_structure/dual_seg_tree.cr

Constructors

Class Method Summary

Instance Method Summary

Constructor Detail

def self.new(values : Array(T), &application : T, T -> T) #

作用素を $f$ とした、$i$ 番目の要素が values[i] の双対セグメント木を作ります。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]

[View source]
def self.new(size : Int, &application : T, T -> T) #

作用素を $f$ とした、要素数 $n$ の双対セグメント木を作ります。

各要素は単位元を表す nil で初期化されます。

seg = NgLib::DualSegTree(Int32).new(5) { |f, x| x + f }
seg # => [nil, nil, nil, nil, nil]

[View source]

Class Method Detail

def self.range_add(values : Array(T)) #

作用素 $f(x) = x + f$ とした双対セグメント木を作ります。


[View source]
def self.range_add(size : Int) #

作用素 $f(x) = x + f$ とした双対セグメント木を作ります。


[View source]
def self.range_chmax(values : Array(T)) #

作用素 $f(x) = \max(f, x)$ とした双対セグメント木を作ります。


[View source]
def self.range_chmax(size : Int) #

作用素 $f(x) = \max(f, x)$ とした双対セグメント木を作ります。


[View source]
def self.range_chmin(values : Array(T)) #

作用素 $f(x) = \min(f, x)$ とした双対セグメント木を作ります。


[View source]
def self.range_chmin(size : Int) #

作用素 $f(x) = \min(f, x)$ とした双対セグメント木を作ります。


[View source]
def self.range_update(values : Array(T)) #

作用素 $f(x) = f$ とした双対セグメント木を作ります。


[View source]
def self.range_update(size : Int) #

作用素 $f(x) = f$ とした双対セグメント木を作ります。


[View source]

Instance Method Detail

def []=(start : Int, count : Int, applicator : T) #

#apply へのエイリアスです。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg[0, 2] = 10
seg # => [11, 12, 3, 4, 5]

[View source]
def []=(range : Range(Int | Nil, Int | Nil), applicator : T) #

#apply へのエイリアスです。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg[0...2] = 10
seg # => [11, 12, 3, 4, 5]

[View source]
def apply(start : Int, count : Int, application : T) #

start 番目から count 個までの各要素に applicator を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.apply(0, 2, 10)
seg # => [11, 12, 3, 4, 5]

[View source]
def apply(range : Range(Int | Nil, Int | Nil), applicator : T) #

range の表す区間に applicator を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.apply(0...2, 10)
seg # => [11, 12, 3, 4, 5]

[View source]
def apply_all(applicator : T) #

すべての要素に application を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.all_apply(10)
seg # => [11, 12, 13, 14, 15]

[View source]
def size : Int32 #
Description copied from module Indexable(T)

Returns the number of elements in this container.


[View source]
def to_s(io : IO) #
Description copied from class Reference

Appends a short String representation of this object which includes its class name and its object address.

class Person
  def initialize(@name : String, @age : Int32)
  end
end

Person.new("John", 32).to_s # => #<Person:0x10a199f20>

[View source]
def unsafe_fetch(index : Int) #
Description copied from module Indexable(T)

Returns the element at the given index, without doing any bounds check.

Indexable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they access elements with #[](index) and #[]?(index).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.


[View source]
def unsafe_put(index : Int, value : T) #
Description copied from module Indexable::Mutable(T)

Sets the element at the given index to value, without doing any bounds check.

Indexable::Mutable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they modify elements with #[]=(index, value).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.


[View source]