haar_lib/typical/double_sigma/
range_prod.rs

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