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要素の積の総和 $\sum_{i = 1}^{N-1} \sum_{j = i+1}^N a_i \times a_j$
8///
9/// **Time complexity** $O(|a|)$
10pub fn sum_of_sum_of_prod<T>(a: Vec<T>) -> T
11where
12    T: Copy + Mul<Output = T> + AddAssign + Zero,
13{
14    let mut ret = T::zero();
15    let mut acc = T::zero();
16
17    for x in a {
18        ret += x * acc;
19        acc += x;
20    }
21
22    ret
23}