尋找數據結構來連續添加數字

-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

回答