D&C

记录一道碰到的笔试题。

题目

给定一个int数组，求其最长的连续递增子序列，但递增过程中可以忽略m个数组元素。在最优子序列长度相同时，以子序列元素之和较小的一个为最优解*。
即实现方法

vector<int> getLongestSubAry(const vector<int>& array, int m)

思路

八成是动态规划，参考最长连续子序列。
需要存储状态：第i个元素的{最优序列，忽略元素个数}
从i向前寻找m个位置的最优解（因为最多只能忽略m个）。假设那个“之前的”元素是array[j]，那如果array[i]>array[j]并且array[j]+1>=当前最优序列长度，则判断限制条件*以确定是否更新最优解。
整个方法的复杂度应该是[latex]O(n*m)[/latex]，其中n为array的长度。

代码

#include <iostream>
#include <vector>
using namespace std;
struct OptmElem{
    vector<int> results;
    int omitCount;
    int getResultCount(){
        return results.size();
    }
};
int getSum(const vector<int>& ary){
    int sum = 0;
    for(int i=0; i<ary.size(); i++)
        sum += ary[i];
    return sum;
}
/**
* Find the longest increasing subarray
* that allows skipping m elements
*/
vector<int> maxSubArray(const vector<int>& array, int m){
    if(array.empty())
        return vector<int>();
    vector<OptmElem> bestResults;
    OptmElem initOptm;
    initOptm.results.push_back(array[0]);
    initOptm.omitCount = m;
    bestResults.push_back(initOptm);
    unsigned long maxLen = 0;
    int optiIndex = 0; //index of optimal result in bestResults
    for(int i=1; i<array.size(); i++){
        vector<int> currBest = {array[i]};
        int omitCount = m;
        for(int j=(i-m>=0)?(i-m):(0); j<i; j++){
            //trace back j steps
            //if omittance limit exceed, continue
            if(bestResults[j].omitCount < (i-j-1)){
                continue;
            }
            if((array[i] > array[j]) && (bestResults[j].getResultCount()+1 >= currBest.size())){
                //new optimal
                if(bestResults[j].getResultCount()+1  == currBest.size()){
                    //on-par result, array that has the smallest sum is the best
                    int oldSum = getSum(currBest);
                    int newSum = getSum(bestResults[j].results) + array[i];
                    if(newSum > oldSum){
                        continue; //omit this best
                    }
                }
                currBest = bestResults[j].results;
                currBest.push_back(array[i]);
                omitCount = bestResults[j].omitCount - (i-j-1);
            }
        }
        OptmElem elem;
        elem.results = currBest;
        elem.omitCount = omitCount;
        bestResults.push_back(elem);
        if(maxLen < currBest.size()){
            maxLen = currBest.size();
            optiIndex = i;
        } else if (maxLen == currBest.size()){
            int oldBestSum = getSum(bestResults[optiIndex].results);
            int currBestSum = getSum(currBest);
            if(currBestSum < oldBestSum){
                optiIndex = i;
            }
        }
    }
    return bestResults[optiIndex].results;
}

本文翻译自https://leetcode.com/articles/recursive-approach-segment-trees-range-sum-queries-lazy-propagation/，如有侵权请直接Email我

简介

什么是线段树(Segment Tree)

线段树是一种二叉树，树中的每一个节点代表一段区间。通常一个节点储存这个区间的一个或多个属性用于后续查询。

为什么要使用线段树（它的特点是什么）?

许多问题需要我们给出数据集在某个区间或者片段内的查询结果。特别是当出现大量、重复的查询时，这类操作会变得冗长或缓慢。一个线段树可以让我们在对数级时间复杂度内得到这类问题的查询结果。
线段树在计算集合学、GIS等领域有相关应用。例如，我们可能会在距离某个中心点/原点附近一段距离的空间范围内有大量的参考点。假设我们需要查询距离原点指定距离范围内的相关参考点。一个普通的查询表需要线性阶的时间来扫描所有的点或所有可能的距离（想一下hash map）。线段树允许我们在对数时间内解决这个问题，并且拥有更少的空间消耗。这类问题被称作 Planar Range Searching。高效解决这类问题是至关重要的，特别是在处理那些快速变换、无法预知的动态数据时（例如，一个空管雷达系统）。
本文稍后会解决区间和查询问题（Range Sum Query Problem）作为一个例子，借此说明线段树是如何节省空间及实时代价。

我们将会使用上图作为一个实例来介绍用于“区间和查询”的线段树它长什么样，以及有何特性。

如何生成一个线段树

我们将数据保存在大小为[latex]n[/latex]的数组arr[] 中。

1. 线段树树的根通常表示整个数据的区间范围，即arr[0:n-1] ；
2. 树的每一个叶节点表示单个元素（或只有一个元素的区间）。因此叶节点表示的数值为arr[0] ,arr[1] 直至arr[n-1] ；
3. 树的非叶节点表示其子节点合并(merge/union)后的结果；
4. 每一个子节点都能表示其父节点一半的区间范围；

一个包含[latex]n[/latex]个元素范围的线段树可以用一个[latex]\approx 4 * n[/latex]大小的数组表示。（其原因在StackOverflow上有详尽的讨论。如果你仍不相信，没关系，我们稍后会进一步讨论。）

怎么（用数组）存呢？

思路很简单：一个索引号为[latex]i[/latex]的节点，他的子节点的索引号为[latex](2*i+1)[/latex]以及[latex](2*i+2)[/latex].

在使用递归方法构建时，线段树非常直观且容易使用。

线段树的递归方法

我们将使用数组tree[] 来保存线段树（用0值初始化）的节点属性。以下是具体的存储方案（使用以0开始的索引号）：

• 树的根节点索引为0，即tree[0]
• 节点tree[i] 的子节点存储在tree[2*i+1] 及tree[2*i+2] 中
• 当数组元素数量不是2的k次方（如2,4,8,16,32…）时，用 0  或null 填充不足的元素值

我们真的需要用0填充么?

不完全是。只是需要保证tree[]足够大，并且初始值都是0，而且不需要担心额外的叶节点没有被处理过。

• 叶节点的索引范围是[latex]2^k-1[/latex]到[latex]2^(k+1)-2[/latex]

我们只需要下列三个方法：

1.根据给定数据构造线段树

void buildSegTree(vector<int>& arr, int treeIndex, int lo, int hi)
{
    if (lo == hi) {                 // 叶节点. 在里面存储数值.
        tree[treeIndex] = arr[lo];
        return;
    }
    int mid = lo + (hi - lo) / 2;   // 子节点，递归进一层.
    buildSegTree(arr, 2 * treeIndex + 1, lo, mid);
    buildSegTree(arr, 2 * treeIndex + 2, mid + 1, hi);
    // 合并构造结果
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
// call this method as buildSegTree(arr, 0, 0, n-1);
// Here arr[] is input array and n is its size.

该方法自下而上地构造整个tree 。当满足条件[latex]lo=hi[/latex]时，我们处理的区间只包含单个元素（即arr[lo] ）。这就是树的叶节点。余下的非叶节点通过合并其子节点的结果构造而成。treeIndex 是当前正在处理的线段树的索引号。

举个例子，上图中的树可以由下面的输入数据构造出：（本文通篇都会使用这个例子）

arr[] = { 18, 17, 13, 19, 15, 11, 20, 12, 33, 25 };

你能猜到本例中的merge 操作是什么吗？在构造完毕后，tree[] 数组看起来是这样的：

tree[] = { 183, 82, 101, 48, 34, 43, 58, 35, 13, 19, 15, 31, 12, 33, 25, 18, 17, 0, 0, 0, 0, 0, 0, 11, 20, 0, 0, 0, 0, 0, 0 };

注意到tree[] 数组末尾的那些0了么？这些就是我们用来填充树，使之成为完全树的null 值（因为我们只有10个叶节点。假若我们有16个叶节点，我们就不需要用null 填充了。你能证明为什么吗？）
注意：对于不同的问题，merge 操作是不同的。在构造线段树之前，你需要仔细考虑到底在线段树的节点中需要存什么数据，以便在合并的时候能够给出最终的结果。

2. 读取/查询数据区间或片段

int querySegTree(int treeIndex, int lo, int hi, int i, int j)
{
    // 查询 arr[i..j]
    if (lo > j || hi < i)               // 片段完全超出范围
        return 0;                       // 表示一个null节点
    if (i <= lo && j >= hi)             // 片段完全在范围内
        return tree[treeIndex];
    int mid = lo + (hi - lo) / 2;       // 当前片段与查询范围有部分重合。递归到深一层。
    if (i > mid)
        return querySegTree(2 * treeIndex + 2, mid + 1, hi, i, j);
    else if (j <= mid)
        return querySegTree(2 * treeIndex + 1, lo, mid, i, j);
    int leftQuery = querySegTree(2 * treeIndex + 1, lo, mid, i, mid);
    int rightQuery = querySegTree(2 * treeIndex + 2, mid + 1, hi, mid + 1, j);
    // 合并查询结果
    return merge(leftQuery, rightQuery);
}
// call this method as querySegTree(0, 0, n-1, i, j);
// Here [i,j] is the range/interval you are querying.
// This method relies on "null" nodes being equivalent to storing zero.

在查询的范围完全匹配当前节点的范围时，该方法返回一个结果。否则，它将深入树的下一层来寻找满足（部分）查询范围的节点。

这就是线段树的美丽所在

在上述例子中，我们试图找到[latex][2,8][/latex]范围内的节点值的和。没有一个区间能直接满足搜索范围[latex][2,8][/latex]。然而，我们发现范围[latex][2,8][/latex]可以由几个小范围[latex][2,2], [3,4], [5,7], [8,8][/latex]来表示。验证一下，我们可以看到索引范围在[latex][2,8][/latex]的节点值，他们的和是[latex]13+19+15+11+20+12+33=123[/latex]。而刚才提到的那些小区间[latex][2,2], [3,4], [5,7], [8,8][/latex]，他们所对应的节点的和是[latex]13+34+43+33=123[/latex].

3.更新元素的值

void updateValSegTree(int treeIndex, int lo, int hi, int arrIndex, int val)
{
    if (lo == hi) {                 // 叶子节点，更新元素值.
        tree[treeIndex] = val;
        return;
    }
    int mid = lo + (hi - lo) / 2;   // 向更深层递归以查找对应节点
    if (arrIndex > mid)
        updateValSegTree(2 * treeIndex + 2, mid + 1, hi, arrIndex, val);
    else if (arrIndex <= mid)
        updateValSegTree(2 * treeIndex + 1, lo, mid, arrIndex, val);
    // 合并更新结果
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
// call this method as updateValSegTree(0, 0, n-1, i, val);
// Here you want to update the value at index i with value val.

这个操作类似于buildSegTree 。我们根据更新请求来更新对应的叶子节点。随后这些变更向上传递到其父节点。

在这个例子中，位于(输入数据中)索引1,3和6的元素，他们的值对应增加了+3, -1与+2。从图中可以看出这些值是如何向上传递更新，直至根节点的。

复杂度分析

我们来看一下build 过程。我们会访问线段树的每个叶节点（对应到输入数组arr[] 中的每个元素）。这就形成了[latex]n[/latex]个叶节点。此外我们还有[latex]n-1[/latex]个非叶节点。因此总共会有约[latex]2*n[/latex]个节点。这样说来整个构造树的过程的会在[latex]O(n)[/latex]即线性时间内完成。
update 过程在达到目标叶节点的过程中，在递归的每一层都会丢弃一半的范围。这个过程类似于二分搜索，需要对数级的时间。在叶节点更新过后，它的每一个直系父节点也都将被更新，这个过程耗费的时间是树的高度的线性级别。
read/query 过程按照深度优先遍历树，寻找符合搜索条件的节点范围。在最优情况下，我们的范围大于或等于根节点的范围，此时直接能从根节点得到结果。最差情况下，我们搜索一个长度为1的范围（对应于线段树中的一个叶节点），此时我们访问的节点个数等于树的高度；即搜索的时间复杂度和树的高度线性相关。

这就是之前说过的：

一个含有[latex]n[/latex]个元素范围的线段树可以用一个大小约为[latex]4*n[/latex]的数组表示

这保证了我们我们生成的线段树是一个完全二叉树，进一步又保证了这棵树高度的上界是输入规模的对数级。
Viola! 不论是read 还是update 的查询都只需要对数级的[latex]O(log_2(n))[/latex]时间，这正是我们想要的。