線段樹題

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代表右子樹的個數

這題很雷，根本就是死亡線段樹