特性：
    线段树将每个长度不为1的区间划分成左右两个区间递归求解，将线段划分为一个树形结构，并通过合并左右区间的信息来得到区间的信息。
    线段树可以在log(n) 的复杂度内实现单点修改，区间修改，区间查询，以及区间求和，求取区间最大最小值的操作。
    比如一个大小为5的数组{10,11,12,13,14}，构建为线段树后结构为：
    线段树 - 图1
    通过观察发现d1保存的为区间[1,5]的和，并且di的左儿子节点为d2i，右儿子节点为d2i+1, 若di表示的区间为[s,t],则di左子节点代表的区间为[s, (s+t)/2], 右子节点代表的区间为[(s+t)/2+1,t]。
    在实现时，考虑用递归实现构建树。设当前根节点为p，若根节点管辖的区间长度为1，则可以根据数组a对应位置初始化节点，否则我们将该区间从中心处分割为两个子区间，分别进入左右子节点递归构建树，最后合并两个子节点的信息。

    1. #include <cstdio>
    2. #include <vector>
    3. //线段树的构造
    4. void build_segment_tree(std::vector<int>& nums,
    5.                         std::vector<int>& value,
    6.                         int pos,
    7.                         int left,
    8.                         int right) {
    9.     if (left == right) {
    10.         value[pos] = nums[left];
    11.         return;
    12.     }
    13.     int mid = (left + right) / 2;
    14.     build_segment_tree(nums, value, 2 * pos + 1, left, mid);
    15.     build_segment_tree(nums, value, 2 * pos + 2, mid + 1, right);
    16.     value[pos] = value[2 * pos + 1] + value[2 * pos + 2];
    17. }
    18. //线段树的遍历
    19. void print_segment_tree(std::vector<int>& value,
    20.                         int pos,
    21.                         int left,
    22.                         int right,
    23.                         int layer) {
    24.     for (int i = 0; i < layer; i++) {
    25.         printf("---");
    26.     }
    27.     printf("[%d  %d] [%d]:   %d\n", left, right, pos, value[pos]);
    28.     if (left == right) {
    29.         return;
    30.     }
    31.     int mid = (left + right) / 2;
    32.     print_segment_tree(value, 2 * pos + 1, left, mid, layer + 1);
    33.     print_segment_tree(value, 2 * pos + 2, mid + 1, right, layer + 1);
    34. }
    35. //线段树的求和
    36. int sum_range_segment_tree(std::vector<int>& value,
    37.                            int pos,
    38.                            int left,
    39.                            int right,
    40.                            int qleft,
    41.                            int qright) {
    42.     if (qleft > right || qright < left) {
    43.         return 0;
    44.     }
    45.     if (qleft <= left && qright >= right) {
    46.         return value[pos];
    47.     }
    48.     int mid = (left + right) / 2;
    49.     return sum_range_segment_tree(value, 2 * pos + 1, left, mid, qleft,
    50.                                   qright) +
    51.            sum_range_segment_tree(value, 2 * pos + 2, mid + 1, right, qleft,
    52.                                   qright);
    53. }
    54. //线段树的更新
    55. void update_segment_tree(std::vector<int>& value,
    56.                          int pos,
    57.                          int left,
    58.                          int right,
    59.                          int index,
    60.                          int new_value) {
    61.     if (left == right && left == index) {
    62.         value[pos] = new_value;
    63.         return;
    64.     }
    65.     int mid = (left + right) / 2;
    66.     if (index <= mid) {
    67.         update_segment_tree(value, 2 * pos + 1, left, mid, index, new_value);
    68.     } else {
    69.         update_segment_tree(value, 2 * pos + 2, mid + 1, right, index,
    70.                             new_value);
    71.     }
    72.     value[pos] = value[2 * pos + 1] + value[2 * pos + 2];
    73. }
    74. int main() {
    75.     std::vector<int> nums;
    76.     for (int i = 0; i < 6; i++) {
    77.         nums.push_back(i);
    78.     }
    79.     std::vector<int> value;
    80.     for (int i = 0; i < 24; i++) {
    81.         value.push_back(0);
    82.     }
    83.     build_segment_tree(nums, value, 0, 0, nums.size() - 1);
    84.     printf("segment tree:\n");
    85.     print_segment_tree(value, 0, 0, nums.size() - 1, 0);
    86.     int sum_range = sum_range_segment_tree(value, 0, 0, nums.size() - 1, 2, 4);
    87.     printf("sum_range [2,5]=%d\n", sum_range);
    88.     update_segment_tree(value, 0, 0, nums.size() - 1, 2, 10);
    89.     printf("segment_tree:\n");
    90.     print_segment_tree(value, 0, 0, nums.size() - 1, 0);
    91.     return 0;
    92. }