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

作者: the_Miracle | 来源:发表于2020-02-02 12:01 被阅读0次

三种一维树状数组
蓝桥杯-2014-B组-10-小朋友排队（拓展树状数组模板）
线段树 + 树状数组 + ST表模板
区间修改区间查询树状数组思想的应用
树状数组
Binary Index Tree
树状数组图文解析
支持区间修改和区间查询的线段树
线段树
Fenwick Tree/B.I.T树状数组算法

已知数列 $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} ^ *)$

三种一维树状数组
单点修改+区间查询最基本的树状数组树状数组入门模板(洛谷P3374 【模板】树状数组1) 区间修改+单点查询...
蓝桥杯-2014-B组-10-小朋友排队（拓展树状数组模板）
使用到了普通的树状数组和拓展的树状数组。普通的只能单点修改和区间查询，利用两次区间查询可以做到单点查询。如果要区间...
线段树 + 树状数组 + ST表模板
线段树区间修改+区间求和 logN 树状数组区间求和+单点修改 logN ST表离线查询区间最值构造Nlo...
区间修改区间查询树状数组思想的应用
已知数列的通项公式为，是的前项和。求（使用高中及以下的知识）。解：设，易知则又即故
树状数组
复习一下树状数组树状数组一种用于处理单点修改和区间查询的数据结构。树状数组C的定义： C[x] = Sum ...
Binary Index Tree
二维差分: 单点修改/询问前缀和: 区间修改/询问区间: 二维树状数组:
树状数组图文解析
树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改、区间求和。 lowbit数组 l...
支持区间修改和区间查询的线段树
这种线段树支持区间修改和区间查询，区间修改的操作通过懒惰标记（lazy tag）实现。一道支持区间修改和区间查询...
线段树
一、线段树建树、单点修改、区间查询二、线段树建树、区间修改、区间查询
Fenwick Tree/B.I.T树状数组算法
树状数组适用范围：给定区间，求最值，求和，区间单点修改。与RMQ不同的是，RMQ一般只用作区间求最值。但在最值方面...

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

相关文章

三种一维树状数组

蓝桥杯-2014-B组-10-小朋友排队（拓展树状数组模板）

线段树 + 树状数组 + ST表模板

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

树状数组

Binary Index Tree

树状数组图文解析

支持区间修改和区间查询的线段树

线段树

Fenwick Tree/B.I.T树状数组算法

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

线段树