敌兵布阵 HDU - 1166

看了一下午+一上午+一下午的 线段树 。   再看着别人的代码打了一下午。 终于过了， 没有系统的学习，让我有点举步维艰的感觉。 反正就坚持下去把，然后不停的寻找新的机会和方法。第一次做线段树，感觉很吃力，不过慢慢刷下来自然会熟悉题型，知道该怎么做。加油！下面我会尽可能的给出注释，一来如果有人看到这篇文章的话，可以理解我的思维，而来我也可以认认真真的分析好每一个函数，每一句话这么写的原因，也加深自己对线段树的理解。

#include <stdio.h>

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int ans=0;

struct node
{
    int l,r,v;  // 存储边界，那么以后寻找该节点对应的区间只要知道编号就可以了。 l代表left，r代表right ,v代表你要存的价值
}sgetree[200000+1000]; // 理论上如果区间内有n个数，那么对应的节点数应该是2^n-1 就够了，看到别人博客都是开4n;
int a[500000+1000];// 这块我感觉数据可能不止5w . 开5w+10就tle ,开50w 就AC 。
char str[100];

// Add函数，把区间（下标）内某个节点的v改变，那么是不是父亲节点，父亲的父亲节点，xxxxxxxx的父亲节点一直到根节点的和是不是一直都要受到影响呢??那么我们怎么样才能把这个影响给消除掉呢（解决问题）？ 那我们必须要找到这个点，才从这个点往上一直递归，这样子是不是就把改变数据带来的影响给消除了呢？仔细思考一下是的啊！ 哈哈。。。好我们老老实实说题目好吧。 做题更重要！毕竟我很蠢啊。。       首先 由main 函数里函数调用传输  index , add 和1  为什么每次要传输1呢 ？  是因为我每次递归的时候，我的儿子节点和我当前的编号有关系，就是2*n+1和2*n的关系了。   那么我先判断终止条件，就是找到对应的index 满足的要求呢，就是l=r=index  对吧！因为每个点代表一个区间，而改最底层的叶子节点就一个数，就代表该下标的，其实这就是规律吧，可以这么理解，因为线段树最终分分分，一直分就会分成只有一个点的区间情况，不可能有重复的单区间，所以，就是这样子了。  那么OK，我们判断完了终止条件，那么终止后我们要做什么呢，就是把值改变，再不变等回溯了就没机会了，所以必须得改变。 上面说了，用递归，用递归这就是构建线段树的关键，线段树很多操作都是递归递归做。 现在我们看如何递归到底层并且把值改变 ，消除改变值带来上面的改变。 递归操作，其实和建树的过程是有相似点的，我们拿到一个下标（一个点的区间）我们要找，肯定先找范围大的，其实这和二分很像，我先看一半的情况，index 会属于左半棵树呢还是右半颗树呢，然后确定了之后再确定是左半颗呢还是右半颗呢，直到最后确定下来。 确定下来后return  返回到它的上一层，那么我再更新父节点的value=左儿子的v+右儿子的v,怎么找到左右儿子，就凭父节点的sgetree的下标和左右儿子的关系来做。 那么我就一路更新回去，直到更新到 根节点。

总结：对单节点进行数据更新，会影响上面所要的操作，那么我们就要通过递归，判断index 和  mid 的关系找到该节点的位置，并且回溯更新值。 那么我相信肯定有人会有疑惑了，为什么不直接把segtree[下标index]给改变呢。 如果是这样，就很难把当前叶子节点改变的影响传递到父亲节点了，所以需要递归去寻找该叶子节点（而不是直接改），递归完后又回溯再做  父亲节点的v 和 左右儿子的关系， 那么这样一层一层上去就可以完成update的任务了，其实这和建树的过程是一样的，只不过通过index的关系，不停的缩小一半一半一半的范围，最终找到节点的l=r=index的情况才会停止。

void Add(int index,int add,int root)
{
    if(sgetree[root].l==index && index==sgetree[root].r)
    {
        sgetree[root].v+=add; return ;
    }
    int mid=(sgetree[root].l+sgetree[root].r)/2;
    if(index > mid)
        Add(index,add,root*2+1);
    else
        Add(index,add,root*2);
    sgetree[root].v=sgetree[root*2].v+sgetree[root*2+1].v;
}

 // 建树build函数，原理是不停的递归，递归完然后回溯保存需要的值。递归函数一定要有终止条件，否则就是死循环。那么终止条件应该是什么呢？根据二叉树的性质，到最后一层的时候就应该终止，其对应的left,right相等,那么该节点就该截止了，因为无法继续分下去了，那么这个节点就代表了这个点（区间长度为1），这个时候left=right，就是你要存储数据的下标了。那么我们就return ；返回到调用它的上一层。     当递归到最后一层时候  语句③ →  语句① →语句② → 语句④ 那么我们就成功的保存了一颗小树的最小值，函数运行到最后一句话，又返回到上一层调用它的地方回到① → ② 一直这么下去，小树慢慢长大变成半颗大树后 ； 又递归的右边的树，然后又重复半颗大树从顶层递归到底层，然后从底层回溯到顶层，每个节点保存儿子的和，一层一层推上去，最后每个节点结构体对应一个left right 同时得到了  [left~right] 的 最小值。 我们可以发现这样递归，树的左右儿子和父亲节点编号存在一定关系，哇那真是太棒了（虽然函数写的时候就这样了）。但便于理解，正是由于有这样良好的规律，我们可以很方便的从顶层遍历到底层，并且在执行一些操作的时候可以排除掉一些情况你就不用去搜索了，否则如果暴力就要花很多时间，或许这就是logn 的原因吧。 

总结： 对于建树的过程中，要传递的参数有区间范围，即left right,还有下一个子节点的sgetree 编号。对于建树过程中，确定终止条件为l=r，并且赋值，再回溯保存下你要求的值（对于这题是求和）。

void build(int l,int r,int root)  
{
    sgetree[root].l=l;  //  不管是不是叶子节点还是非叶子节点，我都要记录，所以把这个语句放在函数最前面
    sgetree[root].r=r;
    if(l==r) ③
    {
        sgetree[root].v=a[l];
        return ;
    }
    else
    {
        int mid=(l+r)/2;
        build(l,mid,root*2);    ①
        build(mid+1,r,root*2+1);   ②
        sgetree[root].v=sgetree[root*2].v+sgetree[root*2+1].v; ④
    }
}

//求区间[l,f]的和，同样这和上面的所有操作都一样，我都需要在main函数调用query 时候 传入 1，然后自顶向下走一圈再自顶向上，再自顶向下，再自底向上走。  依旧是递归，从顶层往下递归，这是线段树的优势，因为线段树操作的时候过滤了无作用的区间。 继续说query 函数 操作 原理。 我要询问区间  l~j  下标的区间和。 这个递归怎么处理比较合适呢？ 我们从简单的入手，  对于第一次寻找时候，如果区间在1~mid 或者 mid+1~n的情况 那么我们就舍弃另一边，因此就有了语句①的操作。如果left<mid && right>mid 的情况下那么我们把所求的区间和分成2部分来求， 一部分是 left~ mid   &&   mid+1~right 求 解这两个区间的和，原因是因为我节点区间对应分配的过程中，是按这样划分的。所以这样做可以求，那么我们继续往下一层递归，最差的情况就是我把每一个都拆分成了单位长度的区间，然后sgetree[root].l=l ,  sgetree[root].r=r 那么我们在前面建树的过程中已经保存了该节点的和，那么直接ans+=sgetree[root].v 那么就完成了， 过程中也可能在某个区间（除了单位长度的区间）这是我们希望得到的，可以缩短递归的深度，已经到了getree[root].l=l ,  sgetree[root].r=r 的情况就直接返回，那么就可以写出下面的 query 函数。            

总结思路：  对于区间求和，  判断当前所求区间left,right和已知区间mid的范围关系， 把区间和拆成多个小区间的和，共有3种情况（见if else 语句）。 对于每一个子区间，又有如上的关系，直到递归到情况sgetree[root].l==l && sgetree[root].r==r  ,,  说明不用再往下递归了，直接ans+=sgetree[root].v 就是和， 那么把一个区间拆成很多个小区间来求和存储在ans 中，并且在过程中省略掉一些不可能的区间，就可以缩短很多的时间，对于n的范围很大的情况下，可以节省了很多时间，因为不需要遍历每一个元素。   只是把子问题保存在结果中，用递归找到子问题的结果， 这个将起来和动态规划有点相似，动态规划是把每一个子问题的最优解都保存下来，不管用不用到，都先保存下来，便于后面的递推。 哇  就这样了，接下来继续做题，然后好好的总结感悟 ， 努力努力努力！

void query(int l,int r,int root) 
{
    //printf("%d-",ans);
    if(sgetree[root].l==l && sgetree[root].r==r)
    {
        ans+=sgetree[root].v;
        //printf("%d-",ans);
        return ;
    }
    int mid=(sgetree[root].l+sgetree[root].r)/2;    ①
    if(r <= mid) query(l,r,root*2);                 ①
    else if(l>=mid+1) query(l,r,root*2+1);            ①
    else
    {
        query(l,mid,root*2);
        query(mid+1,r,root*2+1);
    }
}


int main(void)
{
    int t;
    int n;
    cin >> t;
    for(int kase=1;kase<=t;kase++)
    {
        cin >> n;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]); // 在输入数量比较多的情况下，最好不要用 cin  输入 ， 容易tle 或者跑的比较慢，为了保险还是 这么做；
        printf("Case %d:\n",kase);
        /*for(int i=1;i<=n;i++) //  最好的习惯是检查输入的数据有没有出错，如果输入错误，那么全部OVER，而且极有可能你会找不出BUG。
            printf("%d-",a[i]);*/
        build(1,n,1);  // 建立树的过程，写建树的函数
        while((scanf("%s",str))==1)
        {
            ans=0;
            if(strcmp(str,"End")==0) break; //写成return 0 结果只能返回一次，得牢记break 和 return 的区别，写代码一定要逻辑清楚。
            else if(strcmp(str,"Add")==0) //如果是某个点加上某个值
            {
                int index,add; // 记录下标，和加多少
                cin >> index >> add;
                Add(index,add,1); //写 Add函数 , 传输下标，加多少，以及从1开始
            }
            else if(strcmp(str,"Sub")==0)
            {
                int index,add;
                cin >> index >> add;
                Add(index,-add,1);
            }
            else if(strcmp(str,"Query")==0)
            {
                int x,y;
                cin >> x >> y;
                query(x,y,1);
                printf("%d\n",ans);
            }
        }
    }

}

总结感悟： 这或许是我写的最认真的一篇感悟了，也许是意识到自己太弱了的原因，所以要好好对待每一题，我为我上一年的碌碌无为感到羞耻。

对于线段树问题，最关键的 问题就是去递归下去，这和搜索很像，对线段树的操作几乎都是通过递归完成遍历。其实线段树很暴力的写法，但是是一种合理范围内的暴力。因此。 学好递归，线段树就没什么问题了，最重要的是一个逻辑思维的过程，分析。