線段樹和樹狀數組都是一種基于區間的修改查詢操作。
這兩種修改和查詢操作互相影響，不能獨立編寫。
單值處理，區間查詢
結構體完成
struct node
{
int l,r;
ll sum;
};
struct SegmentTree //單點修改,區間查詢
{
node tr[maxn<<2];
inline void buildInit(int p)
{
}
inline void push_up(int p)
{
}
inline void changeOp(int p,ll v)
{
}
inline void addOp(int p,ll v)
{
}
inline node queryUnion(node a,node b)
{
}
void build(int l,int r,int p)
{
tr[p].l=l,tr[p].r=r;
if(l==r){buildInit(p);return;}
int mid=(l+r)>>1;
build(l,mid,p<<1);build(mid+1,r,p<<1|1);
push_up(p);
}
void change(int p,int t,ll v)
{
if(tr[p].l==tr[p].r){changeOp(p,v);return;}
int mid=(tr[p].l+tr[p].r)>>1;
if(t<=mid) change(p<<1,t,v);
else change(p<<1|1,t,v);
push_up(p);
}
void add(int p,int t,ll v)
{
if(tr[p].l==tr[p].r){addOp(p,v);return;}
int mid=(tr[p].l+tr[p].r)>>1;
if(t<=mid) add(p<<1,t,v);
else add(p<<1|1,t,v);
push_up(p);
}
node query(int p,int lt,int rt)
{
if(tr[p].l>=lt && tr[p].r<=rt){return tr[p];}
int mid=(tr[p].l+tr[p].r)>>1;
if(rt<=mid) return query(p<<1,lt,rt);
if(lt>mid) return query(p<<1|1,lt,rt);
return queryUnion(query(p<<1,lt,rt),query(p<<1|1,lt,rt));
}
}st; 區間修改，單點查詢
這一部分沒有求和，因為可以看成是區間修改區間查詢，并且對單點的區間查詢，故求和是沒有太大意義的。但是可以有對區間的整體進行一系列的一種操作，并對單點進行查詢結果。由于不求和，是以對于樹狀數組來說不好用，主要是線段樹的操作。
最大最小值
對給定區間内每個值進行一個指派操作，獲得目前值與所給值更大或更小的一個，并在之後進行每個值的詢問操作。
最底層存儲初始值，上層用于進行區間的變化存儲！！(線段樹上層不一定需要用于存儲區間的最終結果以查詢時節約時間，單點查詢本身并不花時間，上層可以隻存儲變化結果)
//求最大最小值的建立 max min
ll a[maxn];
ll tree[maxn<<2];
void build(int l,int r,int pos)
{
if(l==r)
{
tree[pos]=a[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,pos<<1);
build(mid+1,r,(pos<<1)+1);
}
//區間修改
void update(int l,int r,int pos,int tl,int tr,ll v)
{
if(l>tr || r<tl)
return ;
if(l>=tl && r<=tr)
{
tree[pos]=max(tree[pos],v);
return ;
}
if(v<tree[pos]) //******剪枝優化******
return ;
int mid=(l+r)/2;
update(l,mid,pos<<1,tl,tr,v);
update(mid+1,r,(pos<<1)+1,tl,tr,v);
}
//查詢，向上查詢修改過的所有過程
ll query(int l,int r,int pos,int tl,int tr)
{
if(l>tr || r<tl)
return -inf; //有負值記得改成-inf
if(l>=tl && r<=tr)
return tree[pos];
int mid=(l+r)/2;
ll lef=query(l,mid,pos<<1,tl,tr);
ll rig=query(mid+1,r,(pos<<1)+1,tl,tr);
return max(tree[pos],max(lef,rig));
}
結構體完成
優化：
1.剪枝優化。 由于在樹上每一個區間代表該區間下面所有區間的值都會被修改成可能的一個值tree[pos],如果需要修改的值在該區間下，并且值比tree[pos]小，則不可能讓需要修改的值成為最大值。故可以剪枝。見上述代碼
2.RMQ：專門用于處理區間極值問題 https://blog.csdn.net/qq_38890926/article/details/81489495 用該方法處理比正常線段樹消耗時間會少一些常數
區間修改，區間查詢
求和：
在需要區間修改和取區間查詢的時候，需要添加一個lazy數組用于記錄查詢點之下的點對目前查詢點的影響。
其中黑色為查詢所到底的部分，黑色、紅色和綠色為修改部分，是以我們能夠得到綠色和黑色部分的值，但是紅色部分的值就得不到，是以我們需要lazy數組存儲紅色部分的值，當查詢到黑色部分時，加上lazy數組中的值來擷取紅色部分。
線段樹
ll a[maxn];
ll biTree[maxn<<2];
ll bcTree[maxn<<2]; //lazy記錄下方的量,隻有push_down 隻影響子樹
void push_up(int pos) //隻會處理原數組
{
biTree[pos]=biTree[pos<<1] + biTree[pos<<1|1]; //求和用加号
}
void push_down(int l,int r,int pos)
{
if(bcTree[pos])
{
bcTree[pos<<1]=bcTree[pos<<1]+bcTree[pos]; //lazy數組的下放
bcTree[pos<<1|1]=bcTree[pos<<1|1]+bcTree[pos];
int mid=(l+r)>>1;
biTree[pos<<1]=biTree[pos<<1]+(mid-l+1)*bcTree[pos]; //lazy數組對bit樹的影響；
biTree[pos<<1|1]=biTree[pos<<1|1]+(r-mid)*bcTree[pos];
bcTree[pos]=0;
}
}
//初始化
void build(int l,int r,int pos)
{
bcTree[pos]=0; //初始化lazy數組
if(l==r) //更新bitree數組
{
biTree[pos]=a[l]; //指派，如果初始值為0，就指派為0
return ;
}
int mid=(l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,pos<<1|1);
push_up(pos); //向上更新
}
//區間修改
void add(int l,int r,int pos,int tl,int tr,ll num)
{
if(l>tr || r<tl)
return;
if(l>=tl && r<=tr)
{
bcTree[pos]=bcTree[pos]+num; //目前部分的添加到lazy中
biTree[pos]=biTree[pos]+(r-l+1)*num; //目前部分區間更新結果
return;
}
push_down(l,r,pos); //下放lazy數組
int mid=(l+r)>>1;
add(l,mid,pos<<1,tl,tr,num);
add(mid+1,r,pos<<1|1,tl,tr,num);
push_up(pos);
}
//區間查詢
ll query(int l,int r,int pos,int tl,int tr)
{
if(l>tr || r<tl)
return 0;
if(l>=tl && r<=tr)
return biTree[pos]; //目前的lazy數組已被處理，不用處理了
push_down(l,r,pos);
int mid=(l+r)>>1;
ll lef=query(l,mid,pos<<1,tl,tr);
ll rig=query(mid+1,r,pos<<1|1,tl,tr);
return lef+rig;
} 結構體完成
struct node
{
int l,r;
ll sum;
ll val;
};
struct SegmentTree //單點修改,區間查詢
{
node tr[maxn<<2];
inline void buildInit(int p)
{
}
inline void push_up(int p)
{
}
inline void push_down(int p)
{
if(tr[p].val!=0)
{
int l=p<<1,r=p<<1|1;
}
}
inline void addOp(int p,ll v)
{
}
inline node queryUnion(node a,node b)
{
}
void build(int l,int r,int p)
{
tr[p].l=l,tr[p].r=r;
tr[p].val=0;
if(l==r){buildInit(p);return;}
int mid=(l+r)>>1;
build(l,mid,p<<1);build(mid+1,r,p<<1|1);
push_up(p);
}
void add(int p,int lt,int rt,ll v)
{
if(tr[p].l>rt || tr[p].r<lt)return;
if(tr[p].l>=lt && tr[p].r<=rt){addOp(p,v);return;}
push_down(p);
int mid=(tr[p].l+tr[p].r)>>1;
add(p<<1,lt,rt,v);add(p<<1|1,lt,rt,v);
push_up(p);
}
node query(int p,int lt,int rt)
{
if(tr[p].l>=lt && tr[p].r<=rt){return tr[p];}
push_down(p);
int mid=(tr[p].l+tr[p].r)>>1;
if(rt<=mid) return query(p<<1,lt,rt);
if(lt>mid) return query(p<<1|1,lt,rt);
return queryUnion(query(p<<1,lt,rt),query(p<<1|1,lt,rt));
}
}st; 樹狀數組
樹狀數組中的兩個操作sum和add操作，由于sum是對一個數組求字首和，add是對某個單點加上v值，是以無論是否是區間操作，對其沒有任何影響。
在調用結果的時候會有不同的調用方式。
l bit0[maxn];
ll bit1[maxn];
//初始化
void init()
{
memset(bit0,0,sizeof(bit0));
memset(bit1,0,sizeof(bit1));
}
//傳回最低位1所在的值
int lowbit(int i)
{
return i&(-i);
}
//字首和求和
ll sum(ll *a,int i)
{
ll s=0;
while(i)
{
s=s+a[i];
i=i-lowbit(i); //求和向前求和
}
return s;
}
//添加某個值到某一位置上
void add(ll *a,int i,ll v)
{
while(i<=n)
{
a[i]=a[i]+v; //添加向上添加
i=i+lowbit(i);
}
}
int main()
{
//目前還不知道怎麼操作呀呀呀呀呀GGGGGGGGGG
}
set值類型的樹狀數組
//set種類，并且求最後的種類數 poj2777
int n;
int a[maxn];
int biTree[maxn<<2];
int bcTree[maxn<<2]; //lazy記錄下方的量,隻有push_down 隻影響子樹
void push_up(int pos) //隻會處理原數組
{
biTree[pos]=biTree[pos<<1] | biTree[pos<<1|1]; //求和用加号,符号要随着需求而定
}
void push_down(int tl,int tr,int pos)
{
if(bcTree[pos])
{
bcTree[pos<<1]=bcTree[pos];
bcTree[pos<<1|1]=bcTree[pos];
biTree[pos<<1]=bcTree[pos];
biTree[pos<<1|1]=bcTree[pos];
bcTree[pos]=0;
}
}
//初始化
void build(int l,int r,int pos)
{
bcTree[pos]=0; //初始化lazy數組
if(l==r) //更新bitree數組
{
biTree[pos]=a[l]; //指派，如果初始值為0，就指派為0
return ;
}
int mid=(l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,pos<<1|1);
push_up(pos); //向上更新
}
//區間設定
void setTree(int l,int r,int pos,int tl,int tr,int num)
{
if(l>tr || r<tl)
return;
if(l>=tl && r<=tr)
{
bcTree[pos]=1<<(num-1); //在設定裡面lazy數組表示目前之下的所有情況
biTree[pos]=(1<<(num-1)); //目前部分的添加
return;
}
push_down(l,r,pos); //下放lazy數組
int mid=(l+r)>>1;
setTree(l,mid,pos<<1,tl,tr,num);
setTree(mid+1,r,pos<<1|1,tl,tr,num);
push_up(pos);
}
//區間查詢
int query(int l,int r,int pos,int tl,int tr)
{
if(l>tr || r<tl)
return 0;
if(l>=tl && r<=tr)
return biTree[pos]; //目前的lazy數組已被處理，不用處理了
push_down(l,r,pos);
int mid=(l+r)>>1;
int lef=query(l,mid,pos<<1,tl,tr);
int rig=query(mid+1,r,pos<<1|1,tl,tr);
return lef|rig; //注意更改符号 按照需求
} 離散化區間bit和結構體存儲資料lazy樹
該段代碼基本顯示了線段樹整體的本質和總的基本功能，以及lazy的用處
int n;
struct area
{
int l,r;
};
area q[maxn];
struct Discretization
{
vector<int> mp;
int len;
void clear(){mp.clear();len=0;}
void add(int val){mp.push_back(val);}
void discrete()
{
sort(mp.begin(),mp.end());
mp.resize(unique(mp.begin(),mp.end())-mp.begin());
len=mp.size();
}
int getPos(int val)
{
int pos=lower_bound(mp.begin(),mp.end(),val)-mp.begin();
if(pos==len)return -1;
else return pos;
}
int getVal(int pos){return mp[pos];}
}disc;
struct node
{
int l,r;
int sum;
int isl,isr;
int lazy;
};
struct SegmentTree //單點修改,區間查詢
{
node tr[maxn<<2];
inline void buildInit(int p)
{
tr[p].sum=0;
tr[p].isl=tr[p].isr=0;
}
inline void push_up(int p)
{
int l=p<<1,r=p<<1|1;
if(tr[l].isr+tr[r].isl!=2)tr[p].sum=tr[l].sum+tr[r].sum;
else tr[p].sum=tr[l].sum+tr[r].sum-1;
tr[p].isl=tr[l].isl;
tr[p].isr=tr[r].isr;
}
inline void push_down(int p)
{
if(tr[p].lazy!=0)
{
int l=p<<1,r=p<<1|1;
tr[l].sum=tr[r].sum=1;
tr[l].isl=tr[l].isr=tr[r].isl=tr[r].isr=1;
tr[l].lazy=tr[r].lazy=1;
tr[p].lazy=0;
}
}
inline void addOp(int p,int v)
{
tr[p].isl=tr[p].isr=1;
tr[p].sum=1;
tr[p].lazy=1;
}
void build(int l,int r,int p)
{
tr[p].l=l,tr[p].r=r;
tr[p].lazy=0;
if(l==r){buildInit(p);return;}
int mid=(l+r)>>1;
build(l,mid,p<<1);build(mid+1,r,p<<1|1);
push_up(p);
}
void add(int p,int lt,int rt,int v)
{
if(tr[p].l>rt || tr[p].r<lt)return;
if(tr[p].l>=lt && tr[p].r<=rt){addOp(p,v);return;}
push_down(p);
int mid=(tr[p].l+tr[p].r)>>1;
add(p<<1,lt,rt,v);add(p<<1|1,lt,rt,v);
push_up(p);
}
}st;
int main()
{
cin>>n;
disc.clear();
for(int i=1;i<=n;i++)
{
cin>>q[i].l>>q[i].r;
q[i].l*=2;
q[i].r*=2;
disc.add(q[i].l);disc.add(q[i].l-1);disc.add(q[i].l+1);
disc.add(q[i].r);disc.add(q[i].r-1);disc.add(q[i].r+1);
}
disc.discrete();
st.build(0,disc.len,1);
for(int i=1;i<=n;i++)
{
int l=q[i].l,r=q[i].r;
l=disc.getPos(l);
r=disc.getPos(r);
st.add(1,l,r,1);
printf("%d%c",st.tr[1].sum,i==n?'\n':' ');
}
return 0;
}
區間合并
在處理取件問題的時候，上層一定需要處理清楚和下層之間的關系，在區間合并的時候記得處理兩個區間喝起來之後具有的共性。
POJ - 3667 記得剪枝！！！即向左，向右走的時候如果已經找到結果就不處理另外一部分。
struct bit
{
int lef;
int rig;
int maxnum;
};
bit biTree[maxn<<2];
int lazy[maxn<<2];
void push_up(int l,int r,int pos)
{
int lef=pos<<1;
int rig=pos<<1|1;
int mid=(l+r)>>1;
int dis_lef=mid-l+1;
int dis_rig=r-mid;
if(dis_lef==biTree[lef].lef)
biTree[pos].lef=biTree[lef].lef+biTree[rig].lef;
else
biTree[pos].lef=biTree[lef].lef;
if(dis_rig==biTree[rig].rig)
biTree[pos].rig=biTree[rig].rig+biTree[lef].rig;
else
biTree[pos].rig=biTree[rig].rig;
biTree[pos].maxnum=max(biTree[lef].rig+biTree[rig].lef,max(biTree[lef].maxnum,biTree[rig].maxnum));
}
void push_down(int l,int r,int pos)
{
if(lazy[pos]!=0)
{
int lef=pos<<1;
int rig=pos<<1|1;
int mid=(l+r)>>1;
if(lazy[pos]==1)
{
biTree[lef].lef=biTree[lef].rig=biTree[lef].maxnum=0;
biTree[rig].lef=biTree[rig].rig=biTree[rig].maxnum=0;
lazy[lef]=lazy[rig]=1;
lazy[pos]=0;
return;
}
if(lazy[pos]==2)
{
biTree[lef].lef=biTree[lef].rig=biTree[lef].maxnum=mid-l+1;
biTree[rig].lef=biTree[rig].rig=biTree[rig].maxnum=r-mid;
lazy[lef]=lazy[rig]=2;
lazy[pos]=0;
return;
}
}
}
void build(int l,int r,int pos)
{
biTree[pos].lef=biTree[pos].rig=biTree[pos].maxnum=r-l+1;
lazy[pos]=0;
if(l==r)
return;
int mid=(l+r)>>1;
build(l,mid,pos<<1);
build(mid+1,r,pos<<1|1);
}
int query(int l,int r,int pos,int dis)
{
if(biTree[pos].maxnum<dis)
return 0;
if(l==r)
return 0;
push_down(l,r,pos);
int mid=(l+r)>>1;
int lef=query(l,mid,pos<<1,dis);
if(lef>0)
return lef;
if(biTree[pos<<1].rig+biTree[pos<<1|1].lef>=dis)
return mid-biTree[pos<<1].rig+1;
int rig=query(mid+1,r,pos<<1|1,dis);
if(rig>0)
return rig;
return 0;
}
void update(int l,int r,int pos,int tl,int tr,int op)
{
if(r<tl || l>tr)
return ;
if(l>=tl && r<=tr)
{
if(op==0)
{
biTree[pos].lef=biTree[pos].rig=biTree[pos].maxnum=0;
lazy[pos]=1;
}
else
{
biTree[pos].lef= biTree[pos].rig=biTree[pos].maxnum=r-l+1;
lazy[pos]=2;
}
return;
}
push_down(l,r,pos);
int mid=(l+r)>>1;
update(l,mid,pos<<1,tl,tr,op);
update(mid+1,r,pos<<1|1,tl,tr,op);
push_up(l,r,pos);
} 區間非重複元素的和
現在給出一系列N個數字A1，A2，...，AN和一些查詢（i，j）（1≤i≤j≤N）。對于每個Query（i，j），您要計算子序列Ai，Ai + 1，...，Aj中不同值的總和。
這個題目看過去的時候和線段樹很相似，但是其實這個題的本質上是需要莫隊進行處理的，因為線段樹無法處理。
也即是線段樹無法處理在一段區間查詢中要丢掉一些中間點的情況，且丢掉的點随着區間不同結果也不同。
莫隊算法：https://blog.csdn.net/qq_38890926/article/details/81435072
區間單調上升序列的求和
考慮數列 1 3 5 7 2 2 4 4 4 3，求取滿足
且i>k的子序列長度為m的序列數。
例如，對于第一個4來說，以它結束的長度為m的子序列數，應該等于它之前每一個小于4且長度為m-1的子序列總數個數和。
需要對每一個這樣的數進行以上操作，我們就自然想到用線段樹記錄這樣的總和以使得尋找k=[1,i-1]的這層循環時間降低到 logn
我們要求和的目标是比其小的數，且在之前已經通路過的。已經通路過這一層排序其實本質是通路次序的排序，故就是a序列按照正常序列順序通路就好。比其小即我們按照從小到大排序，按照排序後的順序去映射到線段樹中的位置，我們就能直接求和該序列之前所有的值，進而得到既在之前已經通路又比其小的值的總和值。
見上升子序列1：https://blog.csdn.net/qq_38890926/article/details/81449455
二維線段樹和樹狀數組
二維的線段樹和樹狀數組本質上就是很多棵線段樹或樹狀數組，在求取有關sum的條件時，如果說我們采用線段樹，可能會導緻占用記憶體空間過大，這個時候通常我們會采用樹狀數組來提高通路效率和空間優化。同理線段樹也可以處理非sum以外操作。
線段樹
極其浪費空間，幾乎不用！！！！
ll tree[maxm][maxn<<2]; //有n個這樣的樹狀數組，每個都可以存儲m個數的區間和
//添加(tl=tr) 支援單點修改，不支援區間修改
void add(int l,int r,int pos,int tl,int tr,int v,int len)
{
if(l>tr || r<tl)
return ;
if(l>=tl && r<=tr)
{
tree[len][pos]=tree[len][pos]+v;
return ;
}
tree[len][pos]=tree[len][pos]+v;
int mid=(l+r)/2;
add(l,mid,pos<<1,tl,tr,v,len);
add(mid+1,r,(pos<<1)|1,tl,tr,v,len);
}
//查詢
ll sum(int l,int r,int pos,int tl,int tr,int len)
{
if(l>tr || r<tl)
return 0;
if(l>=tl && r<=tr)
return tree[len][pos];
int mid=(l+r)/2;
ll lef=sum(l,mid,pos<<1,tl,tr,len);
ll rig=sum(mid+1,r,(pos<<1)|1,tl,tr,len);
return lef+rig;
}
int main()
{
add(1,n,1,l,r,v,len); //該處l=r
sum(1,n,1,l,r,len);
} 帶set和add的二維線段樹
UVA - 11992
struct l
{
int flag;
int v;
};
int treesum[maxm][maxn<<2];
int treemax[maxm][maxn<<2];
int treemin[maxm][maxn<<2];
l lazy[maxm][maxn<<2];
void build(int l,int r,int pos,int row)
{
if(l==r)
{
treemax[row][pos]=treemin[row][pos]=treesum[row][pos]=lazy[row][pos].v=lazy[row][pos].flag=0;
return;
}
treemax[row][pos]=treemin[row][pos]=treesum[row][pos]=lazy[row][pos].v=lazy[row][pos].flag=0;
int mid=(l+r)>>1;
build(l,mid,pos<<1,row);
build(mid+1,r,pos<<1|1,row);
}
void push_up(int pos,int row)
{
treemax[row][pos]=max(treemax[row][pos<<1],treemax[row][pos<<1|1]);
treemin[row][pos]=min(treemin[row][pos<<1],treemin[row][pos<<1|1]);
treesum[row][pos]=treesum[row][pos<<1]+treesum[row][pos<<1|1];
}
void push_down(int l,int r,int pos,int row)
{
if(lazy[row][pos].flag!=0)
{
int lef=pos<<1;
int rig=pos<<1|1;
int mid=(l+r)>>1;
if(lazy[row][pos].flag==1)
{
treesum[row][lef]=treesum[row][lef]+(mid-l+1)*lazy[row][pos].v;
treesum[row][rig]=treesum[row][rig]+(r-mid)*lazy[row][pos].v;
treemax[row][lef]=treemax[row][lef]+lazy[row][pos].v;
treemax[row][rig]=treemax[row][rig]+lazy[row][pos].v;
treemin[row][lef]=treemin[row][lef]+lazy[row][pos].v;
treemin[row][rig]=treemin[row][rig]+lazy[row][pos].v;
if(lazy[row][lef].flag==0)
lazy[row][lef].flag=1;
lazy[row][lef].v=lazy[row][lef].v+lazy[row][pos].v;
if(lazy[row][rig].flag==0)
lazy[row][rig].flag=1;
lazy[row][rig].v=lazy[row][rig].v+lazy[row][pos].v;
lazy[row][pos].v=0;
lazy[row][pos].flag=0;
}
if(lazy[row][pos].flag==2)
{
treesum[row][lef]=(mid-l+1)*lazy[row][pos].v;
treesum[row][rig]=(r-mid)*lazy[row][pos].v;
treemax[row][lef]=lazy[row][pos].v;
treemax[row][rig]=lazy[row][pos].v;
treemin[row][lef]=lazy[row][pos].v;
treemin[row][rig]=lazy[row][pos].v;
lazy[row][lef].flag=2;
lazy[row][lef].v=lazy[row][pos].v;
lazy[row][rig].flag=2;
lazy[row][rig].v=lazy[row][pos].v;
lazy[row][pos].v=0;
lazy[row][pos].flag=0;
}
}
}
void add(int l,int r,int pos,int tl,int tr,int row,int v)
{
if(tl>r || tr<l)
return ;
if(l>=tl && r<=tr)
{
treesum[row][pos]=treesum[row][pos]+(r-l+1)*v;
treemax[row][pos]=treemax[row][pos]+v;
treemin[row][pos]=treemin[row][pos]+v;
lazy[row][pos].v=lazy[row][pos].v+v;
if(lazy[row][pos].flag==0)
lazy[row][pos].flag=1;
return;
}
push_down(l,r,pos,row);
int mid=(l+r)>>1;
add(l,mid,pos<<1,tl,tr,row,v);
add(mid+1,r,pos<<1|1,tl,tr,row,v);
push_up(pos,row);
}
void sset(int l,int r,int pos,int tl,int tr,int row,int v)
{
if(tl>r || tr<l)
return ;
if(l>=tl && r<=tr)
{
treesum[row][pos]=(r-l+1)*v;
treemax[row][pos]=v;
treemin[row][pos]=v;
lazy[row][pos].v=v;
lazy[row][pos].flag=2;
return;
}
push_down(l,r,pos,row);
push_down(l,r,pos,row);
int mid=(l+r)>>1;
sset(l,mid,pos<<1,tl,tr,row,v);
sset(mid+1,r,pos<<1|1,tl,tr,row,v);
push_up(pos,row);
}
int query_sum(int l,int r,int pos,int tl,int tr,int row)
{
if(tl>r || tr<l)
return 0;
if(l>=tl && r<=tr)
{
return treesum[row][pos];
}
push_down(l,r,pos,row);
int mid=(l+r)>>1;
int lef=query_sum(l,mid,pos<<1,tl,tr,row);
int rig=query_sum(mid+1,r,pos<<1|1,tl,tr,row);
return lef+rig;
}
int query_max(int l,int r,int pos,int tl,int tr,int row)
{
if(tl>r || tr<l)
return 0;
if(l>=tl && r<=tr)
{
return treemax[row][pos];
}
push_down(l,r,pos,row);
int mid=(l+r)>>1;
int lef=query_max(l,mid,pos<<1,tl,tr,row);
int rig=query_max(mid+1,r,pos<<1|1,tl,tr,row);
return max(lef,rig);
}
int query_min(int l,int r,int pos,int tl,int tr,int row)
{
if(tl>r || tr<l)
return inf;
if(l>=tl && r<=tr)
{
return treemin[row][pos];
}
push_down(l,r,pos,row);
int mid=(l+r)>>1;
int lef=query_min(l,mid,pos<<1,tl,tr,row);
int rig=query_min(mid+1,r,pos<<1|1,tl,tr,row);
return min(lef,rig);
}
int r,c,m;
int main()
{
while(scanf("%d %d %d",&r,&c,&m)!=EOF)
{
for(int i=1;i<=r;i++)
build(1,c,1,i);
int op;
int r1,w1,r2,w2;
int v;
for(int t=1;t<=m;t++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d %d %d %d %d",&r1,&w1,&r2,&w2,&v);
for(int i=r1;i<=r2;i++)
add(1,c,1,w1,w2,i,v);
continue;
}
if(op==2)
{
scanf("%d %d %d %d %d",&r1,&w1,&r2,&w2,&v);
for(int i=r1;i<=r2;i++)
sset(1,c,1,w1,w2,i,v);
continue;
}
if(op==3)
{
scanf("%d %d %d %d",&r1,&w1,&r2,&w2);
int sum=0,maxnum=0,minnum=inf;
for(int i=r1;i<=r2;i++)
{
sum=sum+query_sum(1,c,1,w1,w2,i);
maxnum=max(maxnum,query_max(1,c,1,w1,w2,i));
minnum=min(minnum,query_min(1,c,1,w1,w2,i));
}
printf("%d %d %d\n",sum,minnum,maxnum);
}
}
}
return 0;
} 老司機樹(Set的優化方法)
老司機樹即關心線段樹的最後一層，并且由于最後一層滿足l,r單調遞增的性質，是以可以存到set中進行查詢，在處理修改等操作時利用set将大部分點合并以降低查詢的複雜度。其他操作都是暴力查詢點，一個一個解決。
struct node //結點
{
int l,r;
mutable ll v; //mutable才能修改set中的值
node(int L,int R=-1,ll V=0):l(L),r(R),v(V){}
bool operator<(const node& b)const{return l<b.l;}
};
struct ODT
{
set<node> s;
inline void init(){s.clear();}
inline void insert(node a){s.insert(a);}
set<node>::iterator split(int pos) //分割操作
{
set<node>::iterator it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;
if(pos>it->r)return s.end();
int l=it->l,r=it->r;
ll v=it->v;
s.erase(it);
s.insert(node(l,pos-1,v));
return s.insert(node(pos,r,v)).first;
}
void assign(int l,int r,ll val)//區間指派,合并操作
{
set<node>::iterator itr=split(r+1),itl=split(l);
s.erase(itl,itr); //删除itl-itr中間的一段
s.insert(node(l,r,val));
}
void add(int l,int r,ll val)
{
set<node>::iterator itr=split(r+1),itl=split(l);
for(;itl!=itr;itl++)itl->v=itl->v+val;
}
ll rank(int l,int r,int k)
{
vector<pair<ll,int> >vp;
set<node>::iterator itr=split(r+1),itl=split(l);
vp.clear();
for(;itl!=itr;itl++)vp.push_back(pair<ll,int>(itl->v,itl->r-itl->l+1));
sort(vp.begin(),vp.end());
for(vector<pair<ll,int> >::iterator it=vp.begin();it!=vp.end();it++)
{
k=k-it->second;
if(k<=0)return it->first;
}
return (ll)-1;
}
ll sum(int l,int r,int ex,int mod)
{
set<node>::iterator itr=split(r+1),itl=split(l);
ll res=0;
for(;itl!=itr;itl++)res=(res+(ll)(itl->r-itl->l+1)*qpow(itl->v,ll(ex),ll(mod)))%mod;
return res;
}
};
ODT odt; 樹狀數組
ll tree[maxn][maxm]; //二維樹狀數組
int lowbit(int i) //最低位運算
{
return i&(-i);
}
void add(int len,int i,ll v) //對第len維進行添加
{
while(i<=n)
{
tree[len][i]=(tree[len][i]+v)%mod; //添加向上添加
i=i+lowbit(i);
}
}
ll sum(int len,int x) //對第len維進行求和
{
ll s=0;
while(x)
{
s=s+tree[len][x];
x=x-lowbit(x); //求和向下求和
}
return s;
}
樹狀數組中的規律
1.給定x，如何如何求x的最低位1？
ll lowbit(ll x) //最低位運算
{
return x&(-x);
} 這非常容易辦到，lowbit(x)也表示了x這個數最低位組成的值。
2.給定[l,r]，如何求取
.？
利用字首和知識，
等價于
。
我們觀察lowbit的性質，我們可以發現lowbit(i)從數學角度統計，其值等于能被最大的2的幂整除的值。也即是i%1==0，i%2==0,....,i%(2^m)==0,i%(2^(m+1))!=0,則lowbit(i)=2^m。故x中有多少個能被2^m整除的數，即有多少個lowbit(i)大于等于2^m(也可以看成一種和),故lowbit(i)=2^m的個數為x/(2^m)-x/(x^(m+1))也即是(x>>m)-(x>>(m+1))個lowbit(i)=2^m的數。
故
等于((x>>m)-(x>>(m+1)) << m),枚舉m即可：
ll sum(ll x)
{
ll ans=0;
for(int i=0;(x>>i);i++) ans=ans+(((x>>i)-(x>>i+1))<<i);
return ans;
}
3.數x，在長度為n的樹狀數組中被多少個數覆寫？
這個問題仔細思考一下就轉化成了如果我們添加一個數到第x位，則哪些位置會被添加該數，也即是樹狀數組的add函數。
void add(int x,ll v)
{
while(i<=n)
{
tree[i]=tree[i]+v; //添加向上添加
i=i+(i&(-i));
}
} 從中我們可以看出問題的答案就是add中while循環被執行的次數。
int times(int x)
{
int ans;
while(i<=n)
{
ans++;
i=i+(i&(-i));
}
return ans;
} 線段樹和樹狀數組的時間優化：
線段樹和樹狀數組的常數是比較大的，尤其是查詢、修改的量大，并且區間較小。
使用線段樹的時候如果題目是關于求和的，我們可以用樹狀數組的字首和進行優化，這樣可以節約大量數組通路的時間。
但是如果線段樹在無法使用樹狀數組進行優化或者樹狀數組也要大量時間的時候，我們就要從具體的操作進行分析減少時間。
優化一：大量相似(相同)區間段查詢
例如：二分加線段樹
在二分的過程中，我們會發現其實當二分到某一端之後會在那一部分密集左右二分變化，這就意味着那一部分的區間操作大部分有相同區間，如果說我們記錄上一次查詢區間位置和獲得值，在下一次查詢時可以直接調用該部分區間以節約大量區間查詢的時間，并在該基礎上進行小幅度修改即可。