haar_lib/typical/double_sigma/
range_prod.rs

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