可爱的数据结构——线段树

前言

什么是数据结构呢？

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关

—-来自百度百科

简单来说，数据结构就是通过合理的方式在计算机中存储数据，来达到修改、查询的目的。

几个例子
（纯个人看法）

朴素的数据结构

数组（-_-）
链表
队列
栈

看起来高端一些的数据结构

矩阵
哈希表（hash）
堆
树状数组

更高级的数据结构

线段树
各种平衡树
主席树

什么是线段树呢？

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

—-依然来自百度百科

换句话说，就是把一个区间变成一个多层的树形结构，以一种二分与递归的思想实现高效的区间操作

一个例子

写一个数据结构，要求支持在O(logn)的时间复杂度内支持区间加与区间和。