算法提高之線段樹

存儲方式

• 線段樹除了最后一層葉子節點以外是一個滿二叉樹
• 類似堆的形式 因此可以用堆來存儲線段樹
• 同時注意到 數組是可以模擬堆的 因此我們可以用一位數組來存儲線段樹
  • 節點編號為u，對應左子樹編號為2 * u，右子樹編號為2 * u + 1
  • 裝逼一點：u<<1 , u<<1 | 1

重要操作(函數)

• pushup
  • 向上返回，下面節點更新后，需要將父節點也更新，即在子節點更新完pushup()一次
• pushdown
  • 向下遞歸，同理
• build
  • 建樹：從1開始建樹大小為{1,n}
    • 從mid分成**{l,mid},{mid+1,r}**兩部分
    • 遞歸建樹
• query
  • 詢問某個性質(看題干)
  • 比如求區間最大值，(如果可以分為兩部分)求兩部分最大值的最大值
• modify
  • 修改某個節點的值
  • 二分找到x的位置