這個博主的線段樹我覺得講的很細了

文章目錄

• 建樹
• 區間查詢，單點修改
• 區間修改，單點查詢
• 區間修改，區間查詢（帶pushdown）
• 乘法線段樹
• 根號線段樹

建樹

struct node{ll l,r;ll sum,mlz,plz; }tree[4*maxn]; inline void bulid(int i,int l.int r) {tree[i].l=1;tree[i].r=r;if(l==r){tree[i].sum=input[i];return ;}int min=(l+r)>>1;bulid(i*2,l,min);bulid(i*2+1,min+1,r);tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; }

區間查詢，單點修改

inline int search(int i,int l,int r){if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;if(tree[i].r<l||tree[i].l>r)return 0;int sum=0;if(tree[i*2].r>=l)sum+=search(i*2,l,r);if(tree[i*2+1].l<=r)sum+=search(i*2+1,l,r);return sum; } inline void add(int i,int dis,int k) {if(tree[i].l==tree[i].r){tree[i].sum+=k;return;}if(dis<=tree[i*2].r)add(i*2,dis,k);else add(i*2+1,dis,k);tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;return ; }

區間修改，單點查詢

inline void add(int i,int l,int r,int k) {if(tree[i].l>=l&&tree[i].r<=r){tree[i].num+=k;return;}if(tree[i*2].r>=l)add(i*2,l,r,k);if(tree[i*2+1].l<=r)add(i*2+1,l,r,k); } void search(int i,int dis){ans+=tree[i].num;if(dis<=tree[i*2].r)search(i*2,dis);if(dis>=tree[i*2+1].l)search(i*2+1,dis); }

區間修改，區間查詢（帶pushdown）

void push_down(int i) {if(tree[i].lz){tree[i*2].lz+=tree[i].lz;tree[i*2+1].lz+=tree[i].lzint mid=(tree[i].l+tree[i].r)/2;tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);tree[i].lz=0;}return 0; } void add(int i,int l,int r,int k){if(tree[i].r<=r&&tree[i].l>=l){tree[i].sum+=k*(tree[i].r-tree[i].l+1);tree[i].lz+=k;return;}push_back(i);if(tree[i*2].r>=l)add(i*2,l,r,k);if(tree[i*2+1].l<=r)add(i*2+1,l,r,k);tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;return 0; } inline int search(int i,int l,int r){if(tree[i].l>=l&&tree[i].r<=r)return tree[i].sum;if(tree[i].r<l||tree[i].l>r)return 0;push_back(i);int sum=0;if(tree[i*2].r>=l)sum+=search(i*2,l,r);if(tree[i*2+1].l<=r)sum+=search(i*2+1,l,r);return sum; }

乘法線段樹

根號線段樹

總結

以上是生活随笔為你收集整理的线段树回顾的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。