在線更新矢量和的數值穩定算法

Question

給定一個矢量v，我想跟蹤其變量sum_v中元素的總和。向量v的每個元素i是加權向量w_i與其他向量d_i的點積。所以，每當d_i發生變化時，v也一樣，每當d_i發生變化時，我都會根據v_i的變化更新sum_v。不幸的是，小數值不穩定性迅速增加。

我可以用什麼有效的技術來防止這種情況？

編輯：現在，只要d_i發生變化，我的算法就會持續更新sum_v。我想保持在log（n）之下，其中n是v的長度

Answer 1

一個解決方案是構建一個完整的二叉樹，使得每個葉子代表v_i的一個元素，父代表他們的孩子。改變v的元素需要對數時間來過濾到sum_v的變化，但是就取消增量而言，其結果在數值上是穩定的，儘管不是取消v的相鄰元素

這是一個有趣的問題，保持它在數值上對兩個問題都是穩定的。