haar_lib/typical/double_sigma/
range_sum.rs

1//! 区間和の総和
2
3/// 区間和の総和
4///
5/// **Time complexity** $O(|a|)$
6///
7/// # Explanation
8/// $$\bigstar = \sum_{1 \le i \le n} \sum_{i \le j \le n} (a_i + \ldots + a_j)$$
9///
10/// 各$a_i$について、それを含む総和$a_x + \ldots + a_i + \ldots + a_y$がいくつあるかを考えると、
11/// これは$i \times (n - i + 1)$回だけあるので、
12/// $$\bigstar = \sum_{1 \le i \le n} i \times (n-i+1) \times a_i$$
13pub fn sum_of_sum_of_range_sum(a: Vec<i64>) -> i64 {
14    let n = a.len();
15    a.into_iter()
16        .enumerate()
17        .map(|(i, x)| x * (i + 1) as i64 * (n - i) as i64)
18        .sum()
19}