区间修改区间查询树状数组思想的应用

2020-02-02 本文已影响0人 the_Miracle

已知数列 $a _ n$ 的通项公式为 $a _ n = n ^ 2 (n \in \mathbb{N} ^ *)$ ， $S _ n$ 是 $a _ n$ 的前 $n$ 项和。求 $S _ n$ （使用高中及以下的知识）。

解：

设 $b _ n = n (n \in \mathbb{N} ^ *)$ ， $T _ n = b _ 1 + (b _ 1 + b _ 2) + \cdots + (b _ 1 + b _ 2 + \cdots + b _ n) (n \in \mathbb{N} ^ *)$

易知 $\sum _{i = 1} ^{n} b _ i = \frac{n ^ 2}{2} + \frac{n}{2}$

则

$\begin{aligned} T _ n &= \sum _{i = 1} ^{n} \sum _{j = 1} ^{i} b _ i \\ &= \sum _{i = 1} ^{n} (\frac{i ^ 2}{2} + \frac{i}{2}) \\ &= \frac{\sum _{i = 1} ^{n} i ^ 2}{2} + \frac{\sum _{i = 1} ^{n} i}{2} \\ &= \frac{S _ n}{2} + \frac{n(n + 1)}{4} \end{aligned}$
又
$\begin{aligned} T _ n &= \sum _{i = 1} ^{n} \sum _{j = 1} ^{i} b _ i \\ &= \sum _{i = 1} ^{n} (n + 1 - i) b _ i \\ &= (n + 1) \sum _{i = 1} ^{n} b _ i - \sum _{i = 1} ^{n}ib_i \\ &= \frac{n(n + 1) ^ 2}{2} - S _ n \end{aligned}$

即
$\begin{aligned} \frac{S _ n}{2} + \frac{n(n + 1)}{4} &= \frac{n(n + 1) ^ 2}{2} - S _ n \\ \frac{3 S _ n}{2} &= \frac{(n + 1)(2 n ^ 2 + 2 n - n)}{4} \\ \frac{3 S _ n}{2} &= \frac{n(n + 1)(2 n + 1)}{4} \\ S _ n &= \frac{n(n + 1)(2 n + 1)}{6} \end{aligned}$

故 $S _ n = \frac{n(n + 1)(2 n + 1)}{6} (n \in \mathbb{N} ^ *)$

区间修改区间查询树状数组思想的应用

猜你喜欢

热点阅读