學習日記21

   今天中午做了一道用樹狀數組優化的dp題。還用了離散化操作。其實，這道題在我看題解的時候看到過，我一直遲遲不做的原因是，我以為這是那道要用高精度的dp題，想等等再做，網上寫的是高精度模闆，我會寫高精度運算，但不熟練。後來一直在思考一個二維樹狀數組的題，這道題，是在一個區間内塗色，一共有兩種顔色，最後問一個區間内的黑色塊的數量，我剛開始根本想不出怎麼用樹狀數組的區間更新區分兩種顔色，分奇數偶數根本行不通，後來想起做過的幾道暴力題，資料量很小，我再觀察這道題，哈哈最大才100萬，直接把區間更新暴力為單點更新，這樣這道題就沒難度了。

   後來還做了一道需要比較多數學運算的樹狀數組題，需要開兩個樹狀數組，分别存放不同的東西，再經過加減乘除運算解決問題。這個比我看的拿到開55個樹狀數組的題少多了，一般的區間更新都是成段更新，但是有的問題是不連續的更新，但也是有規律的。是每隔k個機關更新一次，這樣就可以劃分區間進行更新，但隻對一個樹狀數組進行更新。雖然這個地方我了解的還不太好。如此看來樹狀數組的題型還有好多，我這連基礎都沒完全掌握，還需要不斷努力。