haar_lib/typical/double_sigma/
prod.rs

1//! 2要素の積の総和
2
3use std::ops::{AddAssign, Mul};
4
5use crate::num::one_zero::Zero;
6
7/// 2要素の積の総和
8///
9/// Σ{i = 1 ~ N - 1}Σ{j = i + 1 ~ N} aᵢ * aⱼ
10///
11/// **Time complexity** $O(|a|)$
12pub fn sum_of_sum_of_prod<T>(a: Vec<T>) -> T
13where
14    T: Copy + Mul<Output = T> + AddAssign + Zero,
15{
16    let mut ret = T::zero();
17    let mut acc = T::zero();
18
19    for x in a {
20        ret += x * acc;
21        acc += x;
22    }
23
24    ret
25}