Aleph::Powerful_Array_Policy< T > Struct Template Reference

Policy: "powerful array" sum = sum(cnt[x]^2 * x). More...

#include <tpl_mo_algorithm.H>

Collaboration diagram for Aleph::Powerful_Array_Policy< T >:

Public Types
using	answer_type = long long

Public Member Functions
void	init (const Array< T > &, size_t)
void	add (const Array< T > &data, size_t idx)
void	remove (const Array< T > &data, size_t idx)
answer_type	answer () const

Public Attributes
MapOLhash< T, long long >	cnt
long long	sum = 0

Detailed Description

template<typename T>
struct Aleph::Powerful_Array_Policy< T >

Policy: "powerful array" sum = sum(cnt[x]^2 * x).

For each element x in the current window with count c, the contribution is c^2 * x. We maintain the sum incrementally: add x: sum += (2*cnt+1)*x, then cnt++ remove x: cnt–, then sum -= (2*cnt+1)*x

Template Parameters

T	Element type (must be hashable and arithmetic-like).

Definition at line 452 of file tpl_mo_algorithm.H.

Member Typedef Documentation

answer_type

template<typename T >

using Aleph::Powerful_Array_Policy< T >::answer_type = long long

Definition at line 454 of file tpl_mo_algorithm.H.

Member Function Documentation

add()

template<typename T >

void Aleph::Powerful_Array_Policy< T >::add ( const Array< T > &  data, size_t  idx  )

inline

Definition at line 466 of file tpl_mo_algorithm.H.

References Aleph::Powerful_Array_Policy< T >::cnt, and Aleph::Powerful_Array_Policy< T >::sum.

answer()

template<typename T >

answer_type Aleph::Powerful_Array_Policy< T >::answer ( ) const

inline

Definition at line 480 of file tpl_mo_algorithm.H.

References Aleph::Powerful_Array_Policy< T >::sum.

init()

template<typename T >

void Aleph::Powerful_Array_Policy< T >::init ( const Array< T > &  , size_t    )

inline

Definition at line 459 of file tpl_mo_algorithm.H.

References Aleph::Powerful_Array_Policy< T >::cnt, Aleph::divide_and_conquer_partition_dp(), and Aleph::Powerful_Array_Policy< T >::sum.

remove()

template<typename T >

void Aleph::Powerful_Array_Policy< T >::remove ( const Array< T > &  data, size_t  idx  )

inline

Definition at line 473 of file tpl_mo_algorithm.H.

References Aleph::Powerful_Array_Policy< T >::cnt, and Aleph::Powerful_Array_Policy< T >::sum.

Member Data Documentation

cnt

template<typename T >

MapOLhash<T, long long> Aleph::Powerful_Array_Policy< T >::cnt

Definition at line 456 of file tpl_mo_algorithm.H.

Referenced by Aleph::Powerful_Array_Policy< T >::add(), Aleph::Powerful_Array_Policy< T >::init(), and Aleph::Powerful_Array_Policy< T >::remove().

sum

template<typename T >

long long Aleph::Powerful_Array_Policy< T >::sum = 0

Definition at line 457 of file tpl_mo_algorithm.H.

Referenced by Aleph::Powerful_Array_Policy< T >::add(), Aleph::Powerful_Array_Policy< T >::answer(), Aleph::Powerful_Array_Policy< T >::init(), and Aleph::Powerful_Array_Policy< T >::remove().

---

The documentation for this struct was generated from the following file:

• tpl_mo_algorithm.H