Sqrt Tree

Dẫn vào

Cho ngươi một cái chiều dài vì n danh sách ${\left\langle a_i\right\rangle}_{i=1}^n$ ,Lại cho ngươi một cái thỏa mãn kết hợp luật giải toán $\circ$ ( tỷ như $\gcd,\min,\max,+,\operatorname{and},\operatorname{or},\operatorname{xor}$ Đều thỏa mãn kết hợp luật ), sau đó đối với mỗi một lần khu gian dò hỏi,Chúng ta yêu cầu tính toán $a_l\circ a_{l+1}\circ\dotsb\circ a_{r}$ .

Sqrt Tree có thể ở $O(n\log\log n)$ Thời gian nội dự xử lý, cũng ởThời gian nội trả lời dò hỏi.

Giải thích

Danh sách phân khối

Đầu tiên chúng ta đem toàn bộ danh sách phân thành $O(\sqrt{n})$ Cái khối, mỗi một khối lớn nhỏ vì $O(\sqrt{n})$ .Đối với mỗi cái khối, chúng ta tính toán:

Khối nội tiền tố khu gian dò hỏi
Khối nội hậu tố khu gian dò hỏi
Giữ gìn một cái thêm vào số tổ $\left\langle B_{i,j}\right\rangle$ Tỏ vẻ đệCái khối đến đệCái khối khu gian đáp án.

Cử cái ví dụ, giả thiết $\circ$ Đại biểu toán cộng giải toán,Danh sách vì $\{1,2,3,4,5,6,7,8,9\}$ .

Đầu tiên chúng ta đem danh sách phân thành tam khối, biến thành $\{1,2,3\},\{4,5,6\},\{7,8,9\}$ .

Như vậy mỗi một khối tiền tố khu gian đáp án cùng hậu tố khu gian đáp án phân biệt vì

\begin{aligned} &P_1=\{1,3,6\},S_1=\{6,5,3\}\\ &P_2=\{4,9,15\},S_2=\{15,11,6\}\\ &P_3=\{7,15,24\},S_3=\{24,17,9\}\\ \end{aligned}

Số tổ vì:

B=\begin{bmatrix} 6 & 21 & 45\\ 0 & 15 & 39\\ 0 & 0 & 24\\ \end{bmatrix}

( đối vớiKhông hợp pháp tình huống chúng ta giả thiết đáp án vì 0 )

Hiển nhiên chúng ta có thể ởThời gian nội dự xử lý này đó giá trị, không gian phức tạp độ đồng dạng là.Xử lý tốt lúc sau, chúng ta có thể lợi dụng chúng nó ởThời gian nội trả lời một ít vượt khối dò hỏi. Nhưng đối với những cái đó toàn bộ khu gian đều ở một cái khối nội dò hỏi chúng ta vẫn không thể xử lý, bởi vậy chúng ta còn cần xử lý một ít đồ vật.

Xây dựng một thân cây

Dễ dàng nghĩ đến chúng ta ở mỗi cái khối nội đệ quy mà cấu tạo kể trên kết cấu hòng duy trì khối nội tuần tra. Đối với lớn nhỏ vìKhối chúng ta có thểMà trả lời dò hỏi. Như vậy chúng ta liền kiến ra một thân cây, mỗi một cái giao điểm đại biểu danh sách một cái khu gian. Lá cây giao điểm khu gian chiều dài vìHoặc.Một cái lớn nhỏ vìGiao điểm có $O(\sqrt{k})$ Vóc dáng tiết điểm, vì thế chỉnh cây độ cao là $O(\log\log n)$ ,Mỗi một tầng khu gian tổng trưởng là,Bởi vậy chúng ta xây dựng này cây phức tạp độ là $O(n\log\log n)$ .

Thụ độ cao chứng minh

Căn cứ định nghĩa, thiết “Khống chế”Cái nguyên tố giao điểm tử thụ độ cao vì,Có thể viết ra đệ quy thức:

T(n)=T(\sqrt n)+1

Làm đổi nguyênĐến

T(2^m)=T(2^{\frac m2})+1

Lại định nghĩa,Đại nhập có

S(m)=S(\dfrac m2)+1

Căn cứ chủ định lý, cũng biết $S(m)=O(\log m)$ ,Bởi vậy $T(n)=S(\log n)=O(\log\log n)$ .

Hiện tại chúng ta có thể ở $O(\log\log n)$ Thời gian nội trả lời dò hỏi. Đối với dò hỏi,Chúng ta chỉ cần nhanh chóng tìm được một cái khu gian chiều dài nhỏ nhất giao điểmKhiến choCó thể bao hàm,Như vậyỞPhân khối khu gian trung nhất định là vượt khối, liền có thểMà tính toán đáp án. Tuần tra một lần tổng thể phức tạp độ là $O(\log\log n)$ ,Bởi vì thụ cao là $O(\log\log n)$ .Bất quá chúng ta vẫn có thể ưu hoá cái này quá trình.

Ưu hoá dò hỏi phức tạp độ

Dễ dàng nghĩ đến nhị phân độ cao, sau đó có thểPhán đoán hay không hợp pháp. Như vậy phức tạp độ liền biến thành $O(\log\log\log n)$ .Bất quá chúng ta vẫn có thể tiến thêm một bước gia tốc này một quá trình.

Chúng ta giả thiết

Mỗi một khối lớn nhỏ đều làSố nguyên mịch thứ;
Mỗi một tầng thượng khối lớn nhỏ là tương đồng.

Vì thế chúng ta yêu cầu ở danh sách mạt vị bổ sung một ítNguyên tố, khiến cho nó chiều dài biến thànhSố nguyên thứ mịch. Cứ việc có chút khối khả năng sẽ biến thành nguyên lai gấp hai lớn nhỏ, nhưng như vậy vẫn là $O(\sqrt{k})$ ,Vì thế dự xử lý phân khối phức tạp độ vẫn là.

Hiện tại chúng ta có thể thoải mái mà xác định một cái dò hỏi khu gian hay không bị toàn bộ mà bao hàm ở một cái khối trung. Đối với khu gian( lấy 0 vì khởi điểm ), chúng ta đem điểm cuối viết vì cơ số hai hình thức. Cử một ví dụ, đối với,Cơ số hai tỏ vẻ vì

l = 39_{10} = 100111_2, r = 46_{10} = 101110_2

Chúng ta biết mỗi một tầng khu gian chiều dài là tương đồng, mà phân khối lớn nhỏ cũng là tương đồng ( ở kể trên thí dụ mẫu trung). Này đó khối hoàn toàn bao trùm toàn bộ danh sách, bởi vậy đệ nhất khối đại biểu nguyên tố vì( cơ số hai tỏ vẻ vì), cái thứ hai khối đại biểu nguyên tố khu gian vì( cơ số hai tỏ vẻ vì), lấy này loại suy. Chúng ta phát hiện này đó ở cùng cái khối nội nguyên tố vị trí ở cơ số hai thượng chỉ có sauVị bất đồng ( kể trên thí dụ mẫu trung). Mà thí dụ mẫuCũng chỉ có sauVị bất đồng, bởi vậy bọn họ ở cùng cái khối trung.

Bởi vậy chúng ta yêu cầu kiểm tra khu gian hai cái điểm cuối hay không chỉ có sauVị bất đồng, tức $l\oplus r\le 2^k-1$ .Bởi vậy chúng ta có thể nhanh chóng tìm được đáp án khu gian nơi tầng:

Đối với mỗi cái $i\in [1,n]$ ,Chúng ta tìm đượcTối cao vị thượng;
Hiện tại đối với một cái dò hỏi,Chúng ta tính toán $l\oplus r$ Tối cao vị, như vậy liền có thể nhanh chóng xác định đáp án khu gian nơi tầng.

Như vậy chúng ta liền có thể ởThời gian nội trả lời dò hỏi lạp.

Đổi mới nguyên tố quá trình

Chúng ta có thể ở Sqrt Tree thượng đổi mới nguyên tố, đơn điểm sửa chữa cùng khu gian sửa chữa đều là duy trì.

Đơn điểm sửa chữa

Suy xét một lần đơn điểm phú giá trị thao tác,Chúng ta hy vọng hiệu suất cao đổi mới cái này thao tác tin tức.

Mộc mạc thực hiện

Đầu tiên chúng ta đến xem ở làm một lần đơn điểm sửa chữa sau Sqrt Tree sẽ biến thành bộ dáng gì.

Suy xét một cái chiều dài vìGiao điểm cùng với đối ứng danh sách: $\left\langle P_i\right\rangle,\left\langle S_i\right\rangle,\left\langle B_{i,j}\right\rangle$ .Dễ dàng phát hiện ở $\left\langle P_i\right\rangle$ Cùng $\left\langle S_i \right\rangle$ Trung đều chỉ có $O(\sqrt{l})$ Cái nguyên tố thay đổi. Mà ở $\left\langle B_{i,j}\right\rangle$ Trung tắc cóCái nguyên tố bị thay đổi. Bởi vậy cóCái nguyên tố ở trên cây bị đổi mới. Bởi vậy ở Sqrt Tree thượng đơn điểm sửa chữa phức tạp độ là $O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(n)$ .

Sử dụng Sqrt Tree thay thế B số tổ

Chú ý tới đơn điểm đổi mới bình cảnh ở chỗ đổi mới căn giao điểm $\left\langle B_{i,j}\right\rangle$ .Bởi vậy chúng ta nếm thử dùng một cái khác Sqrt Tree thay thế căn giao điểm $\left\langle B_{i,j}\right\rangle$ ,Xưng này vì.Nó tác dụng cùng nguyên lai 2D số tổ giống nhau, giữ gìn chỉnh đoạn dò hỏi đáp án. Mặt khác phi căn giao điểm vẫn cứ sử dụng $\left\langle B_{i,j}\right\rangle$ Giữ gìn. Chú ý, nếu một cái Sqrt Tree căn giao điểm cóKết cấu, xưng này Sqrt Tree làĐựng hướng dẫn tra cứu;Nếu một cái Sqrt Tree căn giao điểm có $\left\langle B_{i,j}\right\rangle$ Kết cấu, xưng này làKhông có hướng dẫn tra cứu.MàNày cây bản thân là không có hướng dẫn tra cứu.

Bởi vậy chúng ta có thể như vậy đổi mớiThụ:

Ở $O(\sqrt{n})$ Thời gian nội đổi mới $\left\langle P_i\right\rangle$ Cùng $\left\langle S_i\right\rangle$ .
Đổi mới,Nó chiều dài là,Nhưng chúng ta chỉ cần đổi mới trong đó một cái nguyên tố ( cái này nguyên tố đại biểu bị thay đổi khối ), này một bước thời gian phức tạp độ là $O(\sqrt{n})$ ( sử dụng mộc mạc thực hiện thuật toán ).
Tiến vào sinh ra biến hóa tử tiết điểm cũng sử dụng mộc mạc thực hiện thuật toán ở $O(\sqrt{n})$ Thời gian nội đổi mới tin tức.

Chú ý, tuần tra phức tạp độ vẫn là,Bởi vì chúng ta nhiều nhất sử dụngThụ một lần. Vì thế đơn điểm sửa chữa phức tạp độ chính là $O(\sqrt{n})$ .

Đổi mới một cái khu gian

Sqrt Tree cũng duy trì khu gian bao trùm thao tác $\operatorname{Update}(l,r,x)$ ,Tức đem khu gianSố toàn bộ biến thành.Đối này chúng ta có hai loại thực hiện phương thức, trong đó một loại sẽ tiêu phí $O(\sqrt{n}\log\log n)$ Phức tạp độ đổi mới tin tức,Thời gian tuần tra; một loại khác còn lại là $O(\sqrt{n})$ Đổi mới tin tức, nhưng tuần tra thời gian sẽ gia tăng đến $O(\log\log n)$ .

Chúng ta có thể giống đoạn thẳng thụ giống nhau ở Sqrt Tree thượng đánh lười đánh dấu. Nhưng là ở Sqrt Tree thượng có một chút bất đồng. Bởi vì hạ truyền một cái giao điểm lười đánh dấu, phức tạp độ khả năng đạt tới $O(\sqrt{n})$ ,Bởi vậy chúng ta không phải ở dò hỏi khi hầu hạ truyền đánh dấu, mà là xem phụ tiết điểm hay không có đánh dấu, nếu có đánh dấu liền đem nó hạ truyền.

Đệ nhất loại thực hiện

Ở đệ nhất loại thực hiện trung, chúng ta chỉ biết cấp đệTầng giao điểm ( giao điểm khu gian chiều dài vì $O(\sqrt{n})$ ) đánh lười đánh dấu, tại hạ truyền đánh dấu khi hầu trực tiếp đổi mới toàn bộ tử thụ, phức tạp độ vì $O(\sqrt{n}\log\log n)$ .Thao tác quá trình như sau:

Suy xét đệTầng thượng giao điểm, đối với những cái đó bị sửa chữa khu gian hoàn toàn bao hàm giao điểm, cho bọn hắn đánh một cái lười đánh dấu;
Có hai cái khối chỉ có bộ phận khu gian bị bao trùm, chúng ta trực tiếp ở $O(\sqrt{n}\log\log n)$ Thời gian nộiTrùng kiếnNày hai cái khối. Nếu nó bản thân có chứa phía trước sửa chữa lười đánh dấu, liền ở trùng kiến khi hầu thuận tiện hạ truyền đánh dấu;
Đổi mới căn giao điểm $\left\langle P_i\right\rangle$ Cùng $\left\langle S_i\right\rangle$ ,Thời gian phức tạp độ $O(\sqrt{n})$ ;
Trùng kiếnThụ, thời gian phức tạp độ $O(\sqrt{n}\log\log n)$ .

Hiện tại chúng ta có thể hiệu suất cao hoàn thành khu gian sửa chữa. Như vậy như thế nào lợi dụng lười đánh dấu trả lời dò hỏi? Thao tác như sau:

Nếu chúng ta dò hỏi bị bao hàm ở một cái có lười đánh dấu khối nội, có thể lợi dụng lười đánh dấu tính toán đáp án;
Nếu chúng ta dò hỏi bao hàm nhiều khối, như vậy chúng ta chỉ cần quan tâm nhất bên trái cùng nhất bên phải không hoàn chỉnh khối đáp án. Trung gian khối đáp án có thể ởThụ trung tuần tra ( bởi vìThụ ở mỗi lần sửa chữa xong sau sẽ trùng kiến ), phức tạp độ là.

Bởi vậy dò hỏi phức tạp độ vẫn vì.

Đệ nhị loại thực hiện

Tại đây loại thực hiện trung, mỗi một cái giao điểm đều có thể bị đánh thượng lười đánh dấu. Bởi vậy ở xử lý một cái dò hỏi khi hầu, chúng ta yêu cầu suy xét tổ tiên trung lười đánh dấu, như vậy tuần tra phức tạp độ đem biến thành $O(\log\log n)$ .Bất quá đổi mới tin tức phức tạp độ liền sẽ trở nên càng mau. Thao tác như sau:

Bị sửa chữa khu gian hoàn toàn bao hàm khối, chúng ta đem lười đánh dấu tăng thêm đến này đó khối thượng, phức tạp độ $O(\sqrt{n})$ ;
Bị sửa chữa khu gian bộ phận bao trùm khối, đổi mới $\left\langle P_i\right\rangle$ Cùng $\left\langle S_i\right\rangle$ ,Phức tạp độ $O(\sqrt{n})$ ( bởi vì chỉ có hai cái bị sửa chữa khối );
Đổi mớiThụ, phức tạp độ $O(\sqrt{n})$ ( sử dụng đồng dạng đổi mới thuật toán );
Đối với không có hướng dẫn tra cứu tử thụ đổi mới bọn họ $\left\langle B_{i,j}\right\rangle$ ;
Đệ quy mà đổi mới hai cái không có bị hoàn toàn bao trùm khu gian.

Thời gian phức tạp độ là $O(\sqrt{n}+\sqrt{\sqrt{n}}+\dotsb)=O(\sqrt{n})$ .

Thực hiện

Phía dưới thực hiện ở $O(n\log\log n)$ Thời gian nội thành tựu, ởThời gian nội trả lời dò hỏi, ở $O(\sqrt{n})$ Thời gian nội đơn điểm sửa chữa.

SqrtTreeItemop(constSqrtTreeItem&a,constSqrtTreeItem&b);

intlog2Up(intn){
intres=0;
while((1res)n){
res++;
}
returnres;
}

classSqrtTree{
private:
intn,lg,indexSz;
vectorSqrtTreeItem>v;
vectorint>clz,layers,onLayer;
vectorvectorSqrtTreeItem>>pref,suf,between;

voidbuildBlock(intlayer,intl,intr){
pref[layer][l]=v[l];
for(inti=l+1;ir;i++){
pref[layer][i]=op(pref[layer][i-1],v[i]);
}
suf[layer][r-1]=v[r-1];
for(inti=r-2;i>=l;i--){
suf[layer][i]=op(v[i],suf[layer][i+1]);
}
}

voidbuildBetween(intlayer,intlBound,intrBound,intbetweenOffs){
intbSzLog=(layers[layer]+1)>>1;
intbCntLog=layers[layer]>>1;
intbSz=1bSzLog;
intbCnt=(rBound-lBound+bSz-1)>>bSzLog;
for(inti=0;ibCnt;i++){
SqrtTreeItemans;
for(intj=i;jbCnt;j++){
SqrtTreeItemadd=suf[layer][lBound+(jbSzLog)];
ans=(i==j)?add:op(ans,add);
between[layer-1][betweenOffs+lBound+(ibCntLog)+j]=ans;
}
}
}

voidbuildBetweenZero(){
intbSzLog=(lg+1)>>1;
for(inti=0;iindexSz;i++){
v[n+i]=suf[0][ibSzLog];
}
build(1,n,n+indexSz,(1lg)-n);
}

voidupdateBetweenZero(intbid){
intbSzLog=(lg+1)>>1;
v[n+bid]=suf[0][bidbSzLog];
update(1,n,n+indexSz,(1lg)-n,n+bid);
}

voidbuild(intlayer,intlBound,intrBound,intbetweenOffs){
if(layer>=(int)layers.size()){
return;
}
intbSz=1((layers[layer]+1)>>1);
for(intl=lBound;lrBound;l+=bSz){
intr=min(l+bSz,rBound);
buildBlock(layer,l,r);
build(layer+1,l,r,betweenOffs);
}
if(layer==0){
buildBetweenZero();
}else{
buildBetween(layer,lBound,rBound,betweenOffs);
}
}

voidupdate(intlayer,intlBound,intrBound,intbetweenOffs,intx){
if(layer>=(int)layers.size()){
return;
}
intbSzLog=(layers[layer]+1)>>1;
intbSz=1bSzLog;
intblockIdx=(x-lBound)>>bSzLog;
intl=lBound+(blockIdxbSzLog);
intr=min(l+bSz,rBound);
buildBlock(layer,l,r);
if(layer==0){
updateBetweenZero(blockIdx);
}else{
buildBetween(layer,lBound,rBound,betweenOffs);
}
update(layer+1,l,r,betweenOffs,x);
}

SqrtTreeItemquery(intl,intr,intbetweenOffs,intbase){
if(l==r){
returnv[l];
}
if(l+1==r){
returnop(v[l],v[r]);
}
intlayer=onLayer[clz[(l-base)^(r-base)]];
intbSzLog=(layers[layer]+1)>>1;
intbCntLog=layers[layer]>>1;
intlBound=(((l-base)>>layers[layer])layers[layer])+base;
intlBlock=((l-lBound)>>bSzLog)+1;
intrBlock=((r-lBound)>>bSzLog)-1;
SqrtTreeItemans=suf[layer][l];
if(lBlockrBlock){
SqrtTreeItemadd=
(layer==0)?(query(n+lBlock,n+rBlock,(1lg)-n,n))
:(between[layer-1][betweenOffs+lBound+
(lBlockbCntLog)+rBlock]);
ans=op(ans,add);
}
ans=op(ans,pref[layer][r]);
returnans;
}

public:
SqrtTreeItemquery(intl,intr){returnquery(l,r,0,0);}

voidupdate(intx,constSqrtTreeItem&item){
v[x]=item;
update(0,0,n,0,x);
}

SqrtTree(constvectorSqrtTreeItem>&a)
:n((int)a.size()),lg(log2Up(n)),v(a),clz(1lg),onLayer(lg+1){
clz[0]=0;
for(inti=1;i(int)clz.size();i++){
clz[i]=clz[i>>1]+1;
}
inttlg=lg;
while(tlg>1){
onLayer[tlg]=(int)layers.size();
layers.push_back(tlg);
tlg=(tlg+1)>>1;
}
for(inti=lg-1;i>=0;i--){
onLayer[i]=max(onLayer[i],onLayer[i+1]);
}
intbetweenLayers=max(0,(int)layers.size()-1);
intbSzLog=(lg+1)>>1;
intbSz=1bSzLog;
indexSz=(n+bSz-1)>>bSzLog;
v.resize(n+indexSz);
pref.assign(layers.size(),vectorSqrtTreeItem>(n+indexSz));
suf.assign(layers.size(),vectorSqrtTreeItem>(n+indexSz));
between.assign(betweenLayers,vectorSqrtTreeItem>((1lg)+bSz));
build(0,0,n,0);
}
};

Bài tập

CodeChef - SEGPROD

Bổn giao diện chủ yếu dịch tựSqrt Tree - Algorithms for Competitive Programming,Bản quyền hiệp nghị vì CC-BY-SA 4.0.

Bổn giao diện gần nhất đổi mới:2024/10/9 22:38:42,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:Chrogeek,ChungZH,Enter-tainer,iamtwz,mgt,ouuan,PerfectPan,qwqAutomaton,sshwy,Tiphereth-A
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng