寻找数据结构来连续添加数字

-1

就像标题说的，我试图连续添加数字。这里有一个例子：寻找数据结构来连续添加数字

enter image description here

我preatty肯定有这种数据结构，但不记得它叫什么。任何帮助是极大的赞赏。谢谢。

听起来像是在询问[Fenwick树]（https://en.wikipedia.org/wiki/Fenwick_tree）。 – Sneftel 2014-09-02 22:31:31

你能再细说一下吗？你是否总结了从1到N的数字？或者你是否想加入子范围？ – templatetypedef 2014-09-02 22:38:48

是的，我试图添加所有数字包含。 – 2014-09-02 22:42:46

我认为这是一个比数据结构问题更重要的数学问题。 :-)

数字1 + 2 + ... + n的总和等于n（n + 1）/ 2。这个数字被称为第n个triangular number。

希望这会有所帮助！

2014-09-02 22:47:43 templatetypedef

谢谢！我被告知他们是这样的数据结构，但我想这也可以。再次感谢您的帮助！：d – 2014-09-02 22:54:09

这个简单的求和问题的数据结构是一个矫枉过正的问题。如果这个数字是连续的，那么是推动这个的最佳公式。即使连续的序列从像[8 9 10 11 12 13]这样的随机数开始，那么您仍然可以通过((13 * (13 + 1))/2) - ((7 * (7 + 1))/2)来计算它。

此外，如果您需要数据结构，则可以使用Segment Tree来计算范围总和。（当数据不连续时最好适合）

2014-09-03 05:56:03

回答