前言

时隔多日又要跑出来作妖了......现在想想当初要是早点打造自己的“品牌”该多好，自从进入了大三，就会要收拾各种各样的事情，至少没有大一大二这么咸鱼了，因此要写这种技术文章都没有很连续，很固定的。就像我的React Native入门指导还没写完（虽然比不过大佬的技术，但是自己遇到的坑也是有一定的价值滴）。
咳，言归正传，这次直接跳过了中间各种各样的算法，打算先发一发两个有关于树，并且挺实用的算法。主要因为正好自己结课做的也是这个。
注：题目来自我们亲爱老班的OJ，若觉有不妥之地请务必联系我，我可以立马收起来......

线段树

例题：

题目描述

给定N个整数代表某天的成交量，现在要处理M个查询。查询分为以下两类：1、找出第i天至第j天的最高成交量；2、统计第i天至第j天的总成交量。（N和M的值比较大）

输入

输出

样例输入

6 4
2 4 3 1 5 2
1 1 3
2 1 3
1 3 6
2 3 6

样例输出

4 9 5 11

来源

[计科老班]

这里说到了N和M比较大，所以很明显最容易想到的方法：直接扫几遍查询出结果肯定是不行的。
这里我们采用树这种数据结构，将这个每日成交量构建起来。树的叶子部分，可以想象是每天的成交量本身，节点放置的变量max和sum表示该节点最大值和总和，在叶子上也表现为自己本身。
接着通过递归的方式，将两个节点连接到上一个节点中，构成二叉树，此时这个节点的max值为刚刚两个叶子节点的最大值，sum为刚刚两个叶子节点的总和。

看建树代码

int[] Days;
//create tree for search
    private Node CreateLineTree(int L,int R){
        Node current = new Node();
        current.L = L;current.R = R;
        if(L==R){
            current.max = current.sum = Days[L];
            return current;
        }
        int mid = (L+R)/2;
        current.Left = CreateLineTree(L,mid);
        current.Right = CreateLineTree(mid+1,R);
        current.max = Math.max(current.Left.max, current.Right.max);
        current.sum = current.Left.sum + current.Right.sum;
        
        return current;
    }

L和R表示左边的值和右边的值，在该树中组成一个区间，往后查询时就可以根据这个区间进行筛选。

节点结构

class Node{
        int R,L;
        int max,sum;
        Node Left,Right;
    }

查询的代码

//search the sum between L and R
    private int DisplaySum(Node root,int L,int R){
        if(root.L==L&&root.R==R)return root.sum;
        
        if(R<=root.Left.R)return DisplaySum(root.Left,L,R);
        else if(L>=root.Right.L)return DisplaySum(root.Right,L,R);
        else return (DisplaySum(root.Left,L,root.Left.R)+DisplaySum(root.Right,root.Right.L,R));
    }
    
//search the max between L and R
    private int DisplayMax(Node root,int L,int R){
        if(root.L==L&&root.R==R)return root.max;
        
        if(R<=root.Left.R)return DisplayMax(root.Left,L,R);
        else if(L>=root.Right.L)return DisplayMax(root.Right,L,R);
        else return Math.max(DisplayMax(root.Left,L,root.Left.R), DisplayMax(root.Right,root.Right.L,R));
    }

查询处也可以通过求中位数查询，可能大部分人一开始想到的也是这个（包括我），但其实可以直接利用树中已经存在的值进行判断。
核心的地方就在构建这个线段树，大大的缩短了查询的时间，查询的实现方式应该有各种各样的。

后缀树（字典树）

例题：

题目描述

输入一定量的单词，查询某个单词是否是这些输入的单词中的结尾字母（单词）

输入

开头输入数字，后输入相应个数的单词，直到输入0时才结束此程序。

输出

样例输入

3
ella
Arcella
la
6
ella
Cinderella
abc
bc
c
dbc
0

样例输出

3 6

字典树网上应该也有挺多讲解的，其中还涉及到减少树的高度，提高查询效率的问题，我这里没有涉及，只是单纯的将这种后缀树的实现与查询演示了一遍，感兴趣的可以再去百度一下。
这里比较核心的思想是，将你拿到的单个字符串（单词）反转，也就是从后往前的插入树中，这样子的话我们就可以不用关心这些单词的“传入是否有先后”这个问题了。
之后还需要注意的是，因为是将一个字符串（单词）拆成一个个字母，再将它们放到树中作为一个节点的，需要标记这个字母是不是这个字符串（单词）的结束字母。

先看节点结构

class Node extends HashMap<Character,Node>{ //extend to HashMap so that you new it,you new a HashMap as well.
        private static final long serialVersionUID = 1L;    
        boolean isEnd;  //false,when this character is the end of this string,turn it true.
        int count;  //up one when the character go through it.
    }

这里要先放出节点的构造，因为这颗树并不一定是二叉树，节点不确定，而且我们又需要确定下一个节点的位置，所以我用了HashMap，并且是直接继承的方式，这样子在new这个节点的时候其实就相当于new了一个HashMap。（就是懒得写那句很长的语句）
count这个值，应该是每次经过了存在的节点就进行++操作。

看下核心的构建树代码

//create the tree and return the root of tree.
    private Node createTree(Node root,int position){
        char thisChar = one.charAt(position);
        if(root.containsKey(thisChar)){ //you have it
            root.get(thisChar).count++;
            if(position==0){
                root.get(thisChar).isEnd = true;
                return root;
            }
            else createTree(root.get(thisChar),position-1); //not the end,so move to the next node.
        }else{  //you do not have it
            if(position==0){
                root.put(thisChar, new Node());
                root.get(thisChar).isEnd = true;
                return root;
            }else root.put(thisChar, createTree(new Node(),position-1)); //not the end,create a new node.
        }
        
        return root;
    }

需要注意这里要传入一个根节点，从而使得单次操作中的单词都落到了这颗“树”上，还需要一个位置标记，当这个标记为零时就应该结束（return）并将标记设置为true，因为这里我是没有采用将字符串反转，而是直接从该字符串（单词）尾部开始插入。
将插入节点划分成两种情况：这棵树拥有这个节点和这棵树没有这个节点。这样子的话应该会好理解一些。
因为我这个节点直接就是HashMap，所以你看代码的时候可以会有点绕，你可以先用纸笔画一下理清楚关系先，我当时写的时候写到一半突然就迷茫了hhhh，我一开始也没有适应来着，老想着是在当前节点的count进行++操作，其实应该去到下一层。
而且我这样做的话，不需要考虑“第一个节点不放字母”这个问题。

加和代码

//to result
    private int result(Node root){  //BFS
        int sum = 0;
        Queue<Node> list = new LinkedList<Node>();
        list.add(root);
        while(!list.isEmpty()){
            Node current = list.poll(); //out off this queue.
            for(Entry<Character,Node> entry:current.entrySet()) //foreach 
                list.add(entry.getValue());
            if(current.isEnd)sum+=current.count;
        }
        return sum;
    }

请不要在意我那个蹩脚的英语，自己懂系列。
这里要计算的是单个字符串作为别的字符串结尾单词（字符串）的次数，计算的时候要注意，当且仅当这个标记为true时才取出其中的count进行加和运算。
这里我用的是BFS也就是宽度优先搜索算法，不清楚是不是有更简洁的方式，如果有大佬路过的话可以小小提示我，或者指点我一波。（我就老觉得建了树又再从根开始查询，怪怪的，也没有太多的算法经验）

虽然都是老师教的，或者是网上指点才做出来的，自己也没有想出像这样让人惊叹的算法思路。不过有一点可以肯定的是，思想，还是很重要的东西。

结语

咳咳，对于你大胆的想法，我有一个不成熟的建议。
开玩笑。上面就是一个简单的例题演示，如有什么意见/建议，欢迎提出来。芥末是前端方向的，不过这些基础的东西，自己还是要懂得。这些文章更多的是在做自己的笔记同时分享出去，希望能帮到一些同学。
GitHub：https://github.com/Eugenehyj
另有篇关于RN的一些新手心得（待更新）
——“小白”的前端之路