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 ]