From Evernote: 線段樹題 Clipped from: file:/// uva 12501 need pratice T=test case N=cities Q=operations change i j u增加卡路里消耗，也有可能減少卡路里，更會減到變負的(越跑越多卡路里) query查詢 1 5 5 query 1 3 change 2 3 4 query 1 3 query 2 3 query 3 3 極難.... 每個node維護兩個數值a,sum a[1~2]=a[1~1]+a[2~2] a[1~3]=a[1~2]+a[3~3] sum[1~1]=a[1~1] sum[2~2]=a[2~2] sum[3~3]=a[3~3] sum[4~4]=a[4~4] sum[5~5]=a[5~5] sum[1~2]=sum[1~1]+(1)*a[2~2]+sum[2~2] sum[1~3]=sum[1~2]+(2)*a[3~3]+sum[3~3] sum[4~5]=sum[4~4]+(1)*a[5~5]+sum[5~5] sum[1~5]=sum[1~3]+(3)*a[5~5]+sum[4~5] m=(l+r)/2 id=(r-l+1)-(r-l+1)/2 sum[l~r]=sum[l~m]+id*a[m+1~r]+sum[m+1~r] m-m/2代表左子樹的個數 m/2代表右子樹的個數 這題很雷，根本就是死亡線段樹