鑑於其被初始化爲0的數組ARR即ARR [I] = 0，其中0 <我<Ñ更新陣列
兩種操作是在它
更新KRX
執行更新做以下幾點：
for(i=k;i<=r;i++)
{
arr[i]=x;
x+=x;
}
查詢kr
查詢計算以下總和：
for(i=k;i<=r;i++)
{
sum+=arr[i];
}
print(sum);
我的解決辦法：
我想動粗，但它是緩慢的。我想到了分段樹，但是分段樹更新是以恆定的數量執行的，所以它失敗了。什麼可能是一個很好的算法來解決這個問題？
約束
尺寸數組的是< = 10^5
數操作（更新，查詢）< = 10^5
什麼你正在尋找的是懶惰傳播在段樹木。 我們創建一個數組lazy []，其大小與段樹數組的大小相同。我們的想法是，我們可以通過推遲更新來避免遞歸調用，並且只在需要時才進行更新。
我下面的代碼並進行預定義的數據更新與和提取，您可以用主撥弄接受您所需的圖案的用戶數據，並添加微調，比如x + = X等
我建議您打開代碼並逐一閱讀下面的解釋以更好地理解，因爲懶惰傳播通常很難掌握。
工作原理：
要在數組索引從適量（查詢開始）到QE（查詢端）更新線段樹：
- >如果當前段樹節點具有任何掛起 更新，那麼我們分配該節點（lazy_value）* （它表示的時間間隔的長度），並將其子節點的延遲值指定爲new_value
- >如果當前節點的範圍完全位於 更新查詢範圍內。
i) Update the Current node, by assigning it (lazy_value)*(length of interval it represents)
ii) Postpone updates to children by setting lazy values for children nodes as new_value
- >如果當前節點的範圍內更新 範圍重疊，按照相同的方法，因爲上述簡單 更新。
a。重複發生左右兒童。
b。使用左側 的結果和右側呼叫更新當前節點。
現在，當我們使用get_sum過程時，我們還會更新當前節點，如果它有任何掛起更新並推遲更新給子節點。
總的來說，這是很難解釋這裏偷懶傳播的整個工作，但是我希望代碼和解釋的幫助。
更多關於懶惰的傳播，你可以看到
https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/
可以添加問題的約束？就像x，k和r可以採用的值的範圍一樣。 –
使用Fenwick樹保留前綴總和。 – kfx
發佈此類問題需要顯示總數組大小和查詢數等約束條件。解決方案通常與約束緊密相連。 –