線段樹屬于高級資料結構，本文粗略地講解了一下線段樹的模板，大家直接拿去用就好，
long long ls(int x){return x<<1;}
long long rs(int x){return x<<1|1;}
const int kmax = 1e5 + 10;
struct segmenttree
{
long long l,r;//區間d左值，右值
long long sum;//區間和
long long lazy;//懶惰標記
}t[kmax<<2]；
long long a[kmax];
void pushup(int p)
{//區間和等于左半部磁區間和加右半部磁區間和
t[p].sum = t[p<<1].sum + t[p<<1|1].sum;
}
void pushdown(int p)
{
if(t[p].lazy){
//如果有懶惰標志,則向下傳遞
t[ls(p)].sum += t[p].lazy * (t[ls(p)].r - t[ls(p)].l + 1);
t[rs(p)].sum += t[p].lazy * (t[rs(p)].r - t[rs(p)].l + 1);
t[ls(p)].lazy += t[p].lazy;
t[rs(p)].lazy += t[p].lazy;
t[p].lazy = 0;
}
}
void bulid(long long p,long long l,long long r)
{//建樹，呼叫方式build(1,1,n);
t[p].l = l,t[p].r = r;
if(l==r)//如果到達葉節點，則他的值等于原陣列中的數
{
t[p].sum = a[l];
return;
}
long long mid = (l+r)>>1;//否則遞回左半右半區間
build(ls(p),l,mid);
build(rs(p),mid + 1,r);
pushup(p);
}
void change(long long p,long long l,long long r,long long d)
{//區間修改，呼叫方式change(1,l,r,d);
if(l<=t[p].l&&r>=t[p].r)//如果該區間完整覆寫了目標區間，修改并直接回傳
{
t[p].sum += d * (t[p].r - t[p].l + 1);
t[p].lazy += d;
return;
}
pushdown(p);//否則向下傳遞懶惰標記，并遞回左半右半區間
long long mid = (t[p].l + t[p].r) / 2;
if(l<=mid)change(ls(p),l,r,d);//如果有一部分在左區間，遞回左區間
if(r>mid)change(rs(p),l,r,d);//如果有一部分在右區間，遞回右區間
pushup(p);
}
long long query(long long p,long long l,long long r)//當前的結點編號
{//區間求和，呼叫方式query(1,l,r);
if(l<=t[p].l&&r>=t[p].r)return t[p].sum;//如果該區間完整覆寫了目標區間，直接回傳
pushdown(p);//否則向下傳遞懶惰標記，并遞回左半右半區間
long long mid = (t[p].l + t[p].r) / 2;
long long sum = 0;
if(l<=mid)sum+=query(ls(p),l,r);//如果有一部分在左區間，遞回左區間
if(r>mid)sum+=query(rs(p),d,l,r);
return sum;//回傳累加和
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277428.html
標籤：其他