Via FHQ神犇http://fanhq666.blog.163.com/blog/static/81943426201062865551410/

石子合并（每次合并相邻的两堆石子，代价为这两堆石子的重量和，把一排石子合并为一堆，求最小代价）是一个经典的问题。dp可以做到O(n*n)的时间复杂度，方法是：

朴素DP做法

设f[i,j]为合并从i到j的石子所用最小代价。

f[i,j]=min(sum(i,j)+f[i,k]+f[k+1,j])对所有i<=k<j，其中sum(i,j)表示从i到j的石子重量之和。

设上式取等时k的值为w[i,j]，有神牛证明过：w[i,j]>=w[i,j-1],w[i,j]<=w[i+1,j]

这样，枚举k的时候，就有了一个上下界，从而搞掉了一维。

GarsiaWachs算法

而GarsiaWachs算法可以把时间复杂度压缩到O(nlogn)。

具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W,Lemma X,Lemma Y,Lemma Z。

只能说一个概要吧：

设一个序列是A[0..n-1]，每次寻找最小的一个满足A[k-1]<=A[k+1]的k，（方便起见设A[-1]和A[n]等于正无穷大）
那么我们就把A[k]与A[k-1]合并，之后找最大的一个满足A[j]>A[k]+A[k-1]的j,把合并后的值A[k]+A[k-1]插入A[j]的后面。

有定理保证，如此操作后问题的答案不会改变。

举个例子：

186 64 35 32 103

因为35<103，所以最小的k是3，我们先把35和32删除，得到他们的和67，并向前寻找一个第一个超过67的数，把67插入到他后面

186 64（k=3,A[3]与A[2]都被删除了） 103

186 67（遇到了从右向左第一个比67大的数，我们把67插入到他后面） 64 103

186 67 64 103 （有定理保证这个序列的答案加上67就等于原序列的答案）

现在由5个数变为4个数了，继续！

186 （k=2,67和64被删除了）103

186 131（就插入在这里） 103

186 131 103

现在k=2（别忘了，设A[-1]和A[n]等于正无穷大）

234 186

420

最后的答案呢？就是各次合并的重量之和呗。420+234+131+67=852，哈哈，算对了。

证明嘛，基本思想是通过树的最优性得到一个节点间深度的约束，之后 证明操作一次之后的解可以和原来的解一一对应，并保证节点移动之后他所在的 深度不会改变。详见TAOCP。

实现

具体实现这个算法需要一点技巧，精髓在于不停快速寻找最小的k，即维护一个“2-递减序列”

朴素的实现的时间复杂度是O(n*n)，但可以用一个平衡树来优化（好熟悉的优化方法），使得最终复杂度为O(nlogn)

Via http://en.wikipedia.org/wiki/Segment_tree

In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

Applications of the segment tree are in the areas of computational geometry, and geographic information systems.

The segment tree can be generalized to higher dimension spaces as well.

继续阅读→

Via http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Introduction

We often need some sort of data structure to make our algorithms faster. In this article we will discuss the Binary Indexed Trees structure. According to Peter M. Fenwick, this structure was first used for data compression. Now it is often used for storing frequencies and manipulating cumulative frequency tables.

Let's define the following problem: We have n boxes. Possible queries are
1. add marble to box i
2. sum marbles from box k to box l

The naive solution has time complexity of O(1) for query 1 and O(n) for query 2. Suppose we make m queries. The worst case (when all queries are 2) has time complexity O(n * m). Using some data structure (i.e. RMQ) we can solve this problem with the worst case time complexity of O(m log n). Another approach is to use Binary Indexed Tree data structure, also with the worst time complexity O(m log n) — but Binary Indexed Trees are much easier to code, and require less memory space, than RMQ.

Notation

  BIT – Binary Indexed Tree
  MaxVal – maximum value which will have non-zero frequency
  f[i] – frequency of value with index i, i = 1 .. MaxVal
  c[i] – cumulative frequency for index i (f[1] + f[2] + … + f[i])
  tree[i] – sum of frequencies stored in BIT with index i (latter will be described what index means); sometimes we will write tree frequency instead sum of frequencies stored in BIT
  num¯ – complement of integer num (integer where each binary digit is inverted: 0 -> 1; 1 -> 0 )
NOTE: Often we put f[0] = 0, c[0] = 0, tree[0] = 0, so sometimes I will just ignore index 0.
 

Basic idea

Each integer can be represented as sum of powers of two. In the same way, cumulative frequency can be represented as sum of sets of subfrequencies. In our case, each set contains some successive number of non-overlapping frequencies.

idx is some index of BIT. r is a position in idx of the last digit 1 (from left to right) in binary notation. tree[idx] is sum of frequencies from index (idx – 2^r + 1) to index idx (look at the Table 1.1 for clarification). We also write that idx is responsible for indexes from (idx – 2^r + 1) to idx (note that responsibility is the key in our algorithm and is the way of manipulating the tree).

Image 1.3 – tree of responsibility for indexes (bar shows range of frequencies accumulated in top element)

Image 1.4 – tree with tree frequencies

Suppose we are looking for cumulative frequency of index 13 (for the first 13 elements). In binary notation, 13 is equal to 1101. Accordingly, we will calculate c[1101] = tree[1101] + tree[1100] + tree[1000] (more about this later).

Isolating the last digit
NOTE: Instead of "the last non-zero digit," it will write only "the last digit."

There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.

Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have

-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0…0)¯ + 1 = a¯0(1…1) + 1 = a¯1(0…0) = a¯1b.

Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:

           a1b
&      a¯1b
——————–
= (0…0)1(0…0)

继续阅读→