ในวิทยาการคอมพิวเตอร์ปัญหาการค้นหาช่วง (Range Query ) คือการตอบคำถามหลายข้อเกี่ยวกับช่วงขององค์ประกอบภายในอาร์เรย์ อย่างมีประสิทธิภาพ ตัวอย่างเช่น งานทั่วไปที่เรียกว่าการค้นหาค่าต่ำสุดในช่วง (Range Minimum Query ) คือการหาค่าที่เล็กที่สุดภายในช่วงที่กำหนดในรายการตัวเลข

เมื่อมีฟังก์ชัน ที่รับอาร์เรย์เป็นพารามิเตอร์ การค้นหาช่วงในอาร์เรย์จะรับดัชนีสองตัวคือ และและส่งคืนผลลัพธ์ของเมื่อนำไปใช้กับอาร์เรย์ย่อยตัวอย่างเช่น สำหรับฟังก์ชันที่ส่งคืนผลรวมของค่าทั้งหมดในอาร์เรย์ การค้นหาช่วงจะส่งคืนผลรวมของค่าทั้งหมดในช่วงนั้น ${\displaystyle f}$${\displaystyle f_{q}(l,r)}$${\displaystyle a=[a_{1},..,a_{n}]}$${\displaystyle l}$${\displaystyle r}$${\displaystyle f}$${\displaystyle [a_{l},\ldots ,a_{r}]}$${\displaystyle \operatorname {sum} }$${\displaystyle \operatorname {sum} _{q}(l,r)}$${\displaystyle [l,r]}$

การค้นหาผลรวมในช่วงสามารถตอบได้ในเวลาคงที่และพื้นที่เชิงเส้นโดยการคำนวณอาร์เรย์p ล่วงหน้า ที่มีความยาวเท่ากับอินพุต โดยที่สำหรับทุกดัชนีiองค์ประกอบp _iคือผลรวมของ องค์ประกอบ i ตัวแรก ของaจากนั้นสามารถคำนวณการค้นหาใดๆ ได้ดังนี้:$${\displaystyle \operatorname {sum} _{q}(l,r)=p_{r}-p_{l-1}.}$$

กลยุทธ์นี้สามารถขยายไปยังการดำเนินการไบนารี อื่น ๆ ที่มีฟังก์ชันผกผันที่กำหนดไว้อย่างดีและคำนวณได้ง่าย^{[ 1 ]}นอกจากนี้ยังสามารถขยายไปยังมิติที่สูงขึ้นด้วยการประมวลผลล่วงหน้าที่คล้ายกัน^{[ 2 ]} ตัวอย่างเช่น ถ้าp _i,jประกอบด้วยผลรวมของ องค์ประกอบ i × j แรก ของaแล้ว${\displaystyle f}$${\displaystyle f^{-1}}$$${\displaystyle \operatorname {sum} _{q}(l,r,t,b)=p_{r,b}-p_{l-1,b}-p_{r,t-1}+p_{l-1,t-1}.}$$

ส่วนที่ยากกว่าของปัญหานี้คือการดำเนินการค้นหาช่วงข้อมูลบนข้อมูลแบบไดนามิก กล่าวคือ ข้อมูลที่อาจเปลี่ยนแปลงไประหว่างการค้นหาแต่ละครั้ง เพื่อให้สามารถอัปเดตค่าในอาร์เรย์ได้อย่างมีประสิทธิภาพจำเป็นต้องใช้ โครงสร้างข้อมูลที่ซับซ้อนกว่า เช่น เซ็กเมนต์ทรีหรือเฟนวิคทรี

เมื่อฟังก์ชันที่สนใจในการสอบถามช่วงคือ ตัวดำเนินการ เซมิกรุปแนวคิดของจะไม่ถูกกำหนดเสมอไป ดังนั้นกลยุทธ์ในส่วนก่อนหน้านี้จึงใช้ไม่ได้ผลAndrew Yaoแสดงให้เห็น^{[ 3 ]}ว่ามีวิธีแก้ปัญหาที่มีประสิทธิภาพสำหรับการสอบถามช่วงที่เกี่ยวข้องกับตัวดำเนินการเซมิกรุป เขาพิสูจน์ว่าสำหรับค่าคงที่c ใดๆ การประมวลผลล่วงหน้าของเวลาและพื้นที่ช่วยให้สามารถตอบคำถามช่วงบนรายการที่fเป็นตัวดำเนินการเซมิกรุปในเวลา โดยที่เป็น ฟังก์ชันผกผันบางอย่างของฟังก์ชัน Ackermann${\displaystyle f^{-1}}$${\displaystyle \Theta (c\cdot n)}$${\displaystyle \theta (\alpha _{c}(n))}$${\displaystyle \alpha _{c}}$

มีตัวดำเนินการเซมิกรุปบางตัวที่ให้ผลลัพธ์ที่ดีกว่าเล็กน้อย ตัวอย่างเช่น เมื่อสมมติว่าจะส่งคืนดัชนีขององค์ประกอบที่น้อยที่สุด ของ จากนั้นจะหมายถึงการค้นหาช่วงต่ำสุดที่สอดคล้องกัน มีโครงสร้างข้อมูลหลายอย่างที่ช่วยให้สามารถตอบคำถามการค้นหาช่วงต่ำสุดได้ในเวลา โดยใช้การประมวลผลล่วงหน้าในเวลาและพื้นที่หนึ่งในวิธีแก้ปัญหาดังกล่าวขึ้นอยู่กับความเท่าเทียมกันระหว่างปัญหานี้กับปัญหา บรรพบุรุษร่วมที่ต่ำที่สุด${\displaystyle f\in \{\max ,\min \}}$${\displaystyle f=\min }$${\displaystyle \min(A[1..n])}$${\displaystyle A[1..n]}$${\textstyle \min _{i,j}(A)}$${\displaystyle O(1)}$${\displaystyle O(n)}$

ต้นไม้คาร์ทีเซียน ของอาร์เรย์มีรากเป็น และต้นไม้ย่อยซ้ายและขวา เป็นต้นไม้คาร์ทีเซียนของและต้นไม้คาร์ทีเซียนของตามลำดับ การค้นหาค่าต่ำสุดในช่วงคือบรรพบุรุษร่วมที่ต่ำที่สุดในและเนื่องจากสามารถหาบรรพบุรุษร่วมที่ต่ำที่สุดได้ในเวลาคงที่โดยใช้การประมวลผลล่วงหน้าในเวลาและพื้นที่การค้นหาค่าต่ำสุดในช่วงจึงสามารถทำได้เช่นกัน วิธีแก้ปัญหาเมื่อมีลักษณะคล้ายกัน ต้นไม้คาร์ทีเซียนสามารถสร้างได้ในเวลาเชิงเส้น ${\displaystyle T_{A}}$${\displaystyle A[1,n]}$${\displaystyle a_{i}=\min\{a_{1},a_{2},\ldots ,a_{n}\}}$${\displaystyle A[1,i-1]}$${\displaystyle A[i+1,n]}$${\textstyle \min _{i,j}(A)}$${\displaystyle T_{A}}$${\displaystyle a_{i}}$${\displaystyle a_{j}}$${\displaystyle O(n)}$${\displaystyle f=\max }$

ค่าฐานนิยมของอาร์เรย์คือองค์ประกอบที่ปรากฏบ่อยที่สุดในอาร์เรย์นั้น ตัวอย่างเช่น ค่าฐานนิยมของอาร์เรย์คือ${\displaystyle a=[4,5,6,7,4]}$4.ในกรณีที่มีค่าเท่ากัน องค์ประกอบที่ปรากฏบ่อยที่สุดอาจถูกเลือกเป็นค่าฐานนิยม การค้นหาค่าฐานนิยมในช่วงประกอบด้วยการประมวลผลล่วงหน้าเพื่อให้เราสามารถค้นหาค่าฐานนิยมในช่วงใดก็ได้ของมีโครงสร้างข้อมูลหลายแบบที่ถูกคิดค้นขึ้นเพื่อแก้ปัญหานี้ เราสรุปผลลัพธ์บางส่วนไว้ในตารางต่อไปนี้^{[ 1 ]}${\displaystyle A[1,n]}$${\displaystyle A[1,n]}$

แบบสอบถามโหมดช่วง

ช่องว่าง	เวลาสอบถาม	ข้อจำกัด
${\displaystyle O(n^{2-2\เอปไซลอน })}$	${\displaystyle O(n^{\epsilon }\log n)}$	${\displaystyle 0\leq \epsilon \leq {\frac {1}{2}}}$
${\displaystyle O\left({\frac {n^{2}\log \log n}{\log n}}\right)}$	${\displaystyle O(1)}$

เมื่อเร็วๆ นี้ Jørgensen และคณะได้พิสูจน์ขอบเขตล่างของแบบจำลองเซลล์-โพรบสำหรับโครงสร้างข้อมูลใดๆ ที่ใช้เซลล์S ^{[ 4 ]}${\displaystyle \Omega \left({\tfrac {\log n}{\log(Sw/n)}}\right)}$

กรณีนี้มีความน่าสนใจเป็นพิเศษ เนื่องจากการหาค่ามัธยฐานมีการใช้งานหลายอย่าง^{[ 5 ]}ในทางกลับกัน ปัญหาค่ามัธยฐาน ซึ่งเป็นกรณีพิเศษของปัญหาการเลือกสามารถแก้ไขได้ในO ( n ) โดยใช้อัลกอริทึมค่ามัธยฐานของค่ามัธยฐาน^{[ 6 ]}อย่างไรก็ตาม การวางนัยทั่วไปผ่านการค้นหาค่ามัธยฐานในช่วงเพิ่งเกิดขึ้นไม่นาน^{[ 7 ]}การค้นหาค่ามัธยฐานในช่วงที่A, iและjมีความหมายตามปกติ จะส่งคืนองค์ประกอบค่ามัธยฐานของหรือเทียบเท่าควรส่งคืนองค์ประกอบของที่มีอันดับการค้นหาค่ามัธยฐานในช่วงไม่สามารถแก้ไขได้โดยทำตามวิธีการก่อนหน้านี้ที่กล่าวถึงข้างต้น รวมถึงวิธีการของ Yao สำหรับตัวดำเนินการเซมิกรุป^{[ 8 ]}${\displaystyle \operatorname {median} (A,i,j)}$${\displaystyle A[i,j]}$${\displaystyle \operatorname {median} (A,i,j)}$${\displaystyle A[i,j]}$${\displaystyle {\frac {ji}{2}}}$

มีการศึกษาปัญหาดังกล่าวในสองรูปแบบ คือ รูปแบบ ออฟไลน์ซึ่งคำถามที่สนใจทั้งkข้อจะถูกส่งมาพร้อมกัน และรูปแบบที่ทำการประมวลผลล่วงหน้าทั้งหมด รูปแบบออฟไลน์สามารถแก้ไขได้โดยใช้เวลาและพื้นที่จัดเก็บข้อมูลที่เหมาะสม ${\displaystyle O(n\log k+k\log n)}$${\displaystyle O(n\log k)}$

รหัสเทียมต่อไปนี้ของอัลกอริทึม quickselectแสดงวิธีการค้นหาองค์ประกอบที่มีอันดับrในอาร์เรย์ที่ไม่เรียงลำดับขององค์ประกอบที่แตกต่างกัน เพื่อค้นหาค่ามัธยฐานของช่วงที่เรากำหนด^{[ 7 ]}${\displaystyle A[i,j]}$${\displaystyle r={\frac {จิ}{2}}}$

rangeMedian(A, i, j, r) { if A.length() == 1 return A[1] ถ้า A.low ไม่ได้ถูกกำหนดไว้แล้ว m = ค่ามัธยฐาน(A) A.low = [e ใน A | e <= m] A.high = [e ใน A | e > m ] คำนวณจำนวนองค์ประกอบของ A[i, j] ที่เป็นของ A.low ถ้า r <= t ให้ส่งคืนค่า rangeMedian(A.low, i, j, r) มิฉะนั้นให้ส่งคืนค่า rangeMedian(A.high, i, j, rt) } 

ขั้นตอนrangeMedianการแบ่งพาร์ติ ชัน Aโดยใช้Aค่ามัธยฐานของ 's ออกเป็นสองอาร์เรย์A.lowและA.highโดยที่อาร์เรย์แรกประกอบด้วยองค์ประกอบของAที่น้อยกว่าหรือเท่ากับค่ามัธยฐานmและอาร์เรย์หลังประกอบด้วยองค์ประกอบที่เหลือของAถ้าเรารู้ว่าจำนวนองค์ประกอบของที่ลงเอยในคือและจำนวนนี้มากกว่าเราควรค้นหาองค์ประกอบที่มีอันดับใน ต่อไปมิฉะนั้นเราควรค้นหาองค์ประกอบที่มีอันดับใน ในการหาtนั้น เพียงพอที่จะหาดัชนีสูงสุดที่อยู่ในและดัชนีสูงสุดที่ อยู่ในจาก นั้น ต้นทุนรวมสำหรับการค้นหาใดๆ โดยไม่พิจารณาส่วนของการแบ่งพาร์ติชันคือเนื่องจากมีการเรียกซ้ำอย่างมากที่สุด และมีการดำเนินการเพียงจำนวนคงที่ในแต่ละครั้ง (เพื่อให้ได้ค่าของt ควรใช้ การเรียงลำดับเศษส่วน ) หากใช้อัลกอริทึมเชิงเส้นเพื่อค้นหาค่ามัธยฐาน ต้นทุนรวมของการประมวลผลล่วงหน้าสำหรับการค้นหาค่ามัธยฐานช่วงk คือ อัลกอริทึมยังสามารถปรับเปลี่ยนเพื่อแก้ปัญหาเวอร์ชันออนไลน์ ได้ ^{[ 7 ]}${\displaystyle A[i,j]}$A.lowtrrA.low${\displaystyle (rt)}$A.high${\displaystyle m\leq i-1}$${\displaystyle a_{m}}$A.low${\displaystyle l\leq j}$${\displaystyle a_{l}}$A.high${\displaystyle t=lm}$${\displaystyle \log n}$${\displaystyle \log n}$${\displaystyle n\log k}$

การค้นหาองค์ประกอบที่เกิดขึ้นบ่อยในชุดรายการที่กำหนดเป็นหนึ่งในงานที่สำคัญที่สุดในการทำเหมืองข้อมูล การค้นหาองค์ประกอบที่เกิดขึ้นบ่อยอาจเป็นงานที่ทำได้ยากเมื่อรายการส่วนใหญ่มีความถี่ที่คล้ายคลึงกัน ดังนั้น การใช้เกณฑ์ความสำคัญบางอย่างเพื่อตรวจจับรายการดังกล่าวอาจเป็นประโยชน์มากกว่า หนึ่งในอัลกอริทึมที่มีชื่อเสียงที่สุดสำหรับการค้นหาส่วนใหญ่ของอาร์เรย์ได้รับการเสนอโดย Boyer และ Moore ^{[ 9 ]}ซึ่งรู้จักกันในชื่ออัลกอริทึมการลงคะแนนเสียงส่วนใหญ่ของ Boyer–Moore Boyer และ Moore เสนออัลกอริทึมเพื่อค้นหาองค์ประกอบส่วนใหญ่ของสตริง (ถ้ามี) ในเวลาและ พื้นที่ ในบริบทของงานของ Boyer และ Moore และโดยทั่วไปแล้ว องค์ประกอบส่วนใหญ่ในชุดรายการ (เช่น สตริงหรืออาร์เรย์) คือองค์ประกอบที่มีจำนวนอินสแตนซ์มากกว่าครึ่งหนึ่งของขนาดของชุดนั้น ไม่กี่ปีต่อมา Misra และ Gries ^{[ 10 ]}ได้เสนอเวอร์ชันทั่วไปของอัลกอริทึมของ Boyer และ Moore โดยใช้การเปรียบเทียบเพื่อค้นหารายการทั้งหมดในอาร์เรย์ที่มีความถี่สัมพัทธ์มากกว่าเกณฑ์บางอย่าง การค้นหาแบบช่วงส่วนใหญ่ ( range -majority query) คือการค้นหาที่เมื่อกำหนดช่วงย่อยของโครงสร้างข้อมูล (เช่น อาร์เรย์) ที่มีขนาดจะส่งคืนชุดของรายการที่แตกต่างกันทั้งหมดที่ปรากฏมากกว่า (หรือในสิ่งพิมพ์บางฉบับเท่ากับ) ครั้งในช่วงที่กำหนดนั้น ในโครงสร้างต่างๆ ที่รองรับการค้นหาแบบช่วงส่วนใหญ่ค่า สามารถเป็นได้ทั้งแบบคงที่ (ระบุในระหว่างการประมวลผลล่วงหน้า) หรือแบบไดนามิก (ระบุในเวลาค้นหา) แนวทางดังกล่าวจำนวนมากขึ้นอยู่กับข้อเท็จจริงที่ว่า ไม่ว่าขนาดของช่วงจะเป็นเท่าใด สำหรับค่าที่กำหนดจะมีผู้สมัครที่แตกต่างกันได้ มากที่สุด โดยมีความถี่สัมพัทธ์อย่างน้อยโดยการตรวจสอบผู้สมัครแต่ละรายในเวลาคงที่ ทำให้ได้เวลาการค้นหา การค้นหาแบบช่วงส่วนใหญ่สามารถแยกส่วนได้^{[ 11 ]}ในแง่ที่ว่าส่วนใหญ่ในช่วงที่มีพาร์ติชันและต้องเป็นส่วนใหญ่ในหรือ อย่างใดอย่าง หนึ่ง เนื่องจากความสามารถในการแยกส่วนนี้ โครงสร้างข้อมูลบางประเภทจึงสามารถตอบคำถามส่วนใหญ่บนอาร์เรย์หนึ่งมิติได้โดยการค้นหาบรรพบุรุษร่วมที่ต่ำที่สุด (LCA) ของจุดปลายของช่วงคำถามในต้นไม้ช่วงและตรวจสอบความถูกต้องของชุดผู้สมัครสองชุด (ขนาด) จากแต่ละจุดปลายไปยังบรรพบุรุษร่วมที่ต่ำที่สุดในเวลาคงที่ ส่งผลให้เวลาในการค้นหา ลดลง${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle O\left(n\log \left({\frac {1}{\tau }}\right)\right)}$${\displaystyle 0<\tau <1}$${\displaystyle \tau }$${\displaystyle |R|}$${\displaystyle \tau |R|}$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle O(1/\tau )}$${\displaystyle \tau }$${\displaystyle O(1/\tau )}$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle R}$${\displaystyle R_{1}}$${\displaystyle R_{2}}$${\displaystyle \tau }$${\displaystyle R_{1}}$${\displaystyle R_{2}}$${\displaystyle \tau }$${\displaystyle O(1/\tau )}$${\displaystyle O(1/\tau )}$

Gagie et al. ^{[ 12 ]}เสนอโครงสร้างข้อมูลที่รองรับการค้นหาแบบช่วงส่วนใหญ่บน อาร์เรย์สำหรับการค้นหาแต่ละครั้งในโครงสร้างข้อมูลนี้ จะมีการระบุเกณฑ์และช่วงสี่เหลี่ยมและชุดขององค์ประกอบทั้งหมดที่มีความถี่สัมพัทธ์ (ภายในช่วงสี่เหลี่ยมนั้น) มากกว่าหรือเท่ากับจะถูกส่งคืนเป็นผลลัพธ์ โครงสร้างข้อมูลนี้รองรับเกณฑ์แบบไดนามิก (ระบุในเวลาค้นหา) และเกณฑ์การประมวลผลล่วงหน้าซึ่งใช้ในการสร้าง ในระหว่างการประมวลผลล่วงหน้า จะมีการสร้างชุดของ ช่วง แนวตั้งและแนวนอนบนอาร์เรย์ ช่วงแนวตั้งและแนวนอนรวมกันเป็นบล็อกแต่ละบล็อกเป็นส่วนหนึ่งของซูเปอร์บล็อกที่มีขนาดใหญ่กว่าตัวเองเก้าเท่า (สามเท่าของขนาดช่วงแนวนอนของบล็อกและสามเท่าของขนาดช่วงแนวตั้ง) สำหรับแต่ละบล็อกจะมีการจัดเก็บชุดของตัวเลือก (ที่มีองค์ประกอบไม่เกิน) ซึ่งประกอบด้วยองค์ประกอบที่มีความถี่สัมพัทธ์อย่างน้อย(เกณฑ์การประมวลผลล่วงหน้าตามที่กล่าวไว้ข้างต้น) ในซูเปอร์บล็อกที่เกี่ยวข้อง องค์ประกอบเหล่านี้จะถูกจัดเก็บในลำดับที่ไม่เพิ่มขึ้นตามความถี่ และเห็นได้ง่ายว่า องค์ประกอบใดๆ ที่มีความถี่สัมพัทธ์อย่างน้อยในบล็อก จะต้องปรากฏในชุดตัวเลือกของมันการค้นหาแบบเสียงข้างมากแต่ละครั้งจะได้รับการตอบก่อนโดยการค้นหาบล็อกคำถามหรือบล็อกที่ใหญ่ที่สุดที่อยู่ในสี่เหลี่ยมผืนผ้าคำถามที่กำหนดในเวลาที่กำหนด สำหรับบล็อกคำถามที่ได้รับตัวเลือกแรกจะถูกส่งคืน (โดยไม่ผ่านการตรวจสอบ) ในเวลาที่กำหนด ดังนั้นกระบวนการนี้อาจให้ผลลัพธ์ที่ผิดพลาดได้ โครงสร้างข้อมูลอื่นๆ อีกมากมาย (ดังที่กล่าวไว้ด้านล่าง) ได้เสนอวิธีการตรวจสอบตัวเลือกแต่ละตัวในเวลาคงที่ จึงช่วยรักษาเวลาในการค้นหาโดยไม่ให้ผลลัพธ์ที่ผิดพลาด กรณีที่บล็อกคำถามมีขนาดเล็กกว่าจะได้รับการจัดการโดยการจัดเก็บอินสแตนซ์ที่แตกต่างกันของโครงสร้างข้อมูลนี้ในรูปแบบต่อไปนี้: ${\displaystyle \tau }$${\displaystyle m\times n}$${\displaystyle A}$${\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}$${\displaystyle 0<\tau <1}$${\displaystyle \operatorname {R} }$${\displaystyle \tau }$${\displaystyle \alpha }$${\displaystyle m\times n}$${\displaystyle {\frac {9}{\alpha }}}$${\displaystyle {\frac {\อัลฟา }{9}}}$${\displaystyle \alpha }$${\displaystyle \tau }$${\displaystyle O(1)}$${\displaystyle {\frac {9}{\tau }}}$${\displaystyle O(1/\tau )}$${\displaystyle O(1/\tau )}$${\displaystyle 1/\alpha }$${\displaystyle \log \left({\frac {1}{\alpha }}\right)}$

${\displaystyle \beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}}$

โดยที่ ค่าเกณฑ์การประมวลผลล่วงหน้าของอินสแตนซ์ที่ -th อยู่ที่ใดดังนั้น สำหรับบล็อกคำค้นหาที่มีขนาดเล็กกว่าอินสแตนซ์ที่ -th จะถูกค้นหา ดังที่กล่าวไว้ข้างต้น โครงสร้างข้อมูลนี้มีเวลาในการค้นหา และต้องการพื้นที่จำนวนบิตโดยการจัดเก็บสำเนาที่เข้ารหัสแบบ Huffman (โปรดสังเกตตัวประกอบและดูการเข้ารหัสแบบ Huffman ด้วย ) ${\displaystyle \beta }$${\displaystyle i}$${\displaystyle 1/\alpha }$${\displaystyle \lceil \log(1/\tau )\rceil }$${\displaystyle O(1/\tau )}$${\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}$${\displaystyle \log({\frac {1}{\alpha }})}$

Chan et al. ^{[ 13 ]}เสนอโครงสร้างข้อมูลที่สามารถส่งคืนรายการของค่าส่วนใหญ่ทั้งหมดได้ในเวลาที่ต้องการ พื้นที่จำนวนคำ โดยกำหนดอาร์เรย์หนึ่งมิติ ช่วงย่อยของ(ระบุในเวลาสอบถาม) และเกณฑ์ (ระบุในเวลาสอบถาม) เพื่อตอบคำถามดังกล่าว Chan et al. ^{[ 13 ]}เริ่มต้นด้วยการสังเกตว่ามีโครงสร้างข้อมูลที่สามารถส่งคืน รายการที่พบบ่อยที่สุด 10 อันดับแรกในช่วงในเวลาที่ต้องการพื้นที่จำนวนคำ สำหรับอาร์เรย์หนึ่งมิติให้การสอบถามช่วง 10 อันดับแรกแบบด้านเดียวมีรูปแบบสำหรับช่วงสูงสุดของช่วงที่ความถี่ขององค์ประกอบที่แตกต่างกันในยังคงไม่เปลี่ยนแปลง (และเท่ากับ) จะมีการสร้างส่วนของเส้นตรงแนวนอน ช่วง -ของส่วนของเส้นตรงนี้สอดคล้องกับและมีค่า -เท่ากับเนื่องจากการเพิ่มแต่ละองค์ประกอบลงใน จะเปลี่ยนความถี่ขององค์ประกอบที่แตกต่างกันเพียงหนึ่งเดียว กระบวนการดังกล่าวจึงสร้างส่วนของเส้นตรง นอกจากนี้ สำหรับเส้นตรงแนวตั้งเส้นตรงแนวนอนทั้งหมดที่ตัดกับเส้นตรงนั้นจะถูกจัดเรียงตามความถี่ โปรดทราบว่า เส้นตรงแนวนอนแต่ละเส้นที่มีช่วง -interval จะสอดคล้องกับองค์ประกอบที่แตกต่างกันเพียงหนึ่งเดียวในโดยที่การค้นหาอันดับสูงสุด k สามารถตอบได้โดยการยิงรังสีแนวตั้งและรายงานเส้นตรงแนวนอนแรกที่ตัดกับรังสีนั้น (โปรดจำไว้จากข้างต้นว่าเส้นตรงเหล่านี้ถูกจัดเรียงตามความถี่แล้ว) ตามเวลา ${\displaystyle A}$${\displaystyle R}$${\displaystyle A}$${\displaystyle \tau }$${\displaystyle \tau }$${\displaystyle O(1/\tau )}$${\displaystyle O(n\log n)}$${\displaystyle O(k)}$${\displaystyle O(n)}$${\displaystyle A[0,..,n-1]}$${\displaystyle A[0..i]{\text{ for }}0\leq i\leq n-1}$${\displaystyle A[0..i]{\text{ through }}A[0..j]}$${\displaystyle e}$${\displaystyle A}$${\displaystyle f}$${\displaystyle x}$${\displaystyle [i,j]}$${\displaystyle y}$${\displaystyle f}$${\displaystyle A}$${\displaystyle O(n)}$${\displaystyle x=i}$${\displaystyle x}$${\displaystyle [\ell ,r]}$${\displaystyle e}$${\displaystyle A}$${\displaystyle A[\ell ]=e}$${\displaystyle x=i}$${\displaystyle k}$${\displaystyle O(k)}$

Chan et al. ^{[ 13 ]}สร้างต้นไม้ช่วง (range tree) เป็นครั้งแรก โดยที่แต่ละโหนดแตกแขนงจะเก็บสำเนาโครงสร้างข้อมูลที่อธิบายไว้ข้างต้นไว้หนึ่งชุด สำหรับการค้นหา top-k ช่วงด้านเดียว และแต่ละใบจะแสดงถึงองค์ประกอบจากโครงสร้างข้อมูล top-k ที่แต่ละโหนดจะถูกสร้างขึ้นโดยอิงจากค่าที่มีอยู่ในต้นไม้ย่อยของโหนดนั้น และมีจุดประสงค์เพื่อตอบคำถาม top-k ช่วงด้านเดียว โปรดทราบว่าสำหรับอาร์เรย์หนึ่งมิติสามารถสร้างต้นไม้ช่วงได้โดยการแบ่งออกเป็นสองส่วนและเรียกซ้ำในทั้งสองส่วน ดังนั้นแต่ละโหนดของต้นไม้ช่วงที่ได้จะแสดงถึงช่วง นอกจากนี้ยังสามารถเห็นได้ว่าต้นไม้ช่วงนี้ต้องการพื้นที่จำนวนคำ เนื่องจากมีระดับ และแต่ละระดับมีโหนด ยิ่งไปกว่านั้น เนื่องจากที่แต่ละระดับของต้นไม้ช่วง โหนดทั้งหมดมีองค์ประกอบทั้งหมดของในต้นไม้ย่อย และเนื่องจากมีระดับ ความซับซ้อนของพื้นที่ของต้นไม้ช่วงนี้จึงเป็น ${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$${\displaystyle \ell }$${\displaystyle 2^{\ell }}$${\displaystyle \ell }$${\displaystyle n}$${\displaystyle A}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$

โดยใช้โครงสร้างนี้การค้นหาช่วงส่วนใหญ่บนจะได้รับการตอบดังนี้ ขั้นแรกบรรพบุรุษร่วมที่ต่ำที่สุด (LCA) ของโหนดใบและจะถูกค้นหาในเวลาคงที่ โปรดทราบว่ามีโครงสร้างข้อมูลที่ต้องการพื้นที่บิตซึ่งสามารถตอบคำถาม LCA ได้ในเวลา^{[ 14 ]}ให้แทน LCA ของและโดยใช้และ ตามความสามารถในการแยกส่วนของการค้นหาช่วงส่วนใหญ่ (ดังที่อธิบายไว้ข้างต้นและใน^{[ 11 ]} ) การค้นหาช่วงแบบสองด้านสามารถแปลงเป็นการค้นหาช่วงสูงสุด k ด้านเดียวสองรายการ (จากถึงและ) การค้นหาช่วงสูงสุด k ด้านเดียวสองรายการนี้จะส่งคืนองค์ประกอบที่พบบ่อยที่สุด 10 อันดับแรก ( ) ในแต่ละช่วงที่เกี่ยวข้องในเวลา องค์ประกอบที่พบบ่อยเหล่านี้ประกอบขึ้นเป็นชุดของผู้สมัครสำหรับ-ส่วนใหญ่ในซึ่งมีผู้สมัครบางรายที่อาจเป็นผลบวกเท็จ จากนั้นผู้สมัครแต่ละคนจะได้รับการประเมินในเวลาคงที่โดยใช้โครงสร้างข้อมูลพื้นที่เชิงเส้น (ตามที่อธิบายไว้ใน Lemma 3 ใน^{[ 15 ]} ) ซึ่งสามารถกำหนดได้ใน เวลาว่าช่วงย่อยที่กำหนดของอาร์เรย์มีอย่างน้อยอินสแตนซ์ขององค์ประกอบเฉพาะ หรือ ไม่ ${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle A[0..n-1]}$${\displaystyle 0\leq i\leq j\leq n}$${\displaystyle i}$${\displaystyle j}$${\displaystyle O(n)}$${\displaystyle O(1)}$${\displaystyle z}$${\displaystyle i}$${\displaystyle j}$${\displaystyle z}$${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle z}$${\displaystyle i}$${\displaystyle j}$${\displaystyle 1/\tau }$${\displaystyle O(1/\tau )}$${\displaystyle \tau }$${\displaystyle A[i..j]}$${\displaystyle O(1/\tau )}$${\displaystyle O(1)}$${\displaystyle A}$${\displaystyle q}$${\displaystyle e}$

Gagie et al. ^{[ 16 ]}เสนอโครงสร้างข้อมูลที่รองรับการสอบถามโดยที่เมื่อกำหนดโหนดสองโหนดและในต้นไม้ จะสามารถรายงานรายการองค์ประกอบที่มีความถี่สัมพัทธ์มากกว่าบนเส้นทางจากไปยังได้ กล่าวอย่างเป็นทางการมากขึ้น ให้เป็นต้นไม้ที่มีป้ายกำกับซึ่งแต่ละโหนดมีป้ายกำกับจากตัวอักษรขนาดให้แทนป้ายกำกับของโหนดในให้แทนเส้นทางที่ไม่ซ้ำกันจากไปยังในซึ่งโหนดตรงกลางจะถูกแสดงรายการตามลำดับที่เยี่ยมชม เมื่อกำหนดและเกณฑ์คงที่ (ระบุในระหว่างการประมวลผลล่วงหน้า) การสอบถามจะต้องส่งคืนชุดของป้ายกำกับทั้งหมดที่ปรากฏมากกว่า ครั้งใน ${\displaystyle u}$${\displaystyle v}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$${\displaystyle T}$${\displaystyle \sigma }$${\displaystyle label(u)\in [1,\dots ,\sigma ]}$${\displaystyle u}$${\displaystyle T}$${\displaystyle P_{uv}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle T}$${\displaystyle T}$${\displaystyle 0<\tau <1}$${\displaystyle Q(u,v)}$${\displaystyle \tau |P_{uv}|}$${\displaystyle P_{uv}}$

ในการสร้างโครงสร้างข้อมูลนี้ ขั้นแรก จะทำการ ทำเครื่องหมายโหนดโดยสามารถทำได้โดยการทำเครื่องหมายโหนดใดๆ ที่มีระยะห่างอย่างน้อยจากด้านล่างของสามค่า (ความสูง) และความลึกหารลงตัวด้วยหลังจากนั้น จะสังเกตได้ว่าระยะห่างระหว่างแต่ละโหนดกับบรรพบุรุษที่ทำเครื่องหมายไว้ที่ใกล้ที่สุดนั้นน้อยกว่าสำหรับโหนดที่ทำเครื่องหมายไว้ จะมีการจัดเก็บ ลำดับต่างๆ (เส้นทางไปยังโหนดราก) ไว้ ${\displaystyle {O}(\tau n)}$${\displaystyle \lceil 1/\tau \rceil }$${\displaystyle \lceil 1/\tau \rceil }$${\displaystyle 2\lceil 1/\tau \rceil }$${\displaystyle x}$${\displaystyle \log(depth(x))}$${\displaystyle P_{i}(x)}$

${\displaystyle P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle }$

โดยที่ส่งคืนป้ายกำกับของผู้ปกครองโดยตรงของโหนดกล่าวอีกนัยหนึ่ง สำหรับแต่ละโหนดที่ทำเครื่องหมายไว้ ชุดของเส้นทางทั้งหมดที่มีความยาวเป็นกำลังสอง (บวกหนึ่งสำหรับตัวโหนดเอง) ไปยังรากจะถูกจัดเก็บไว้ ยิ่งไปกว่านั้น สำหรับแต่ละชุดของผู้สมัคร ส่วนใหญ่ทั้งหมด จะถูกจัดเก็บไว้ โดยเฉพาะอย่างยิ่งประกอบด้วยชุดของ เสียงข้างมาก -ทั้งหมดในหรือป้ายกำกับที่ปรากฏมากกว่าครั้งในจะเห็นได้ง่ายว่าชุดของผู้สมัครสามารถมีป้ายกำกับที่แตกต่างกันได้มากที่สุดสำหรับแต่ละGagie et al. ^{[ 16 ]}ตั้งข้อสังเกตว่าชุดของเสียงข้างมาก -ทั้งหมดในเส้นทางจากโหนดที่ทำเครื่องหมายไว้ไปยังบรรพบุรุษตัวใดตัวหนึ่งจะรวมอยู่ในบาง(Lemma 2 ใน^{[ 16 ]} ) เนื่องจากความยาวของเท่ากับดังนั้นจึงมีสำหรับซึ่งความยาวอยู่ระหว่างโดยที่คือระยะทางระหว่าง x และ z การมีอยู่ของ ดังกล่าวหมายความว่าเสียงข้างมาก - ในเส้นทางจากไปยัง จะต้องเป็นเสียงข้างมาก - ในและดังนั้น จะต้องปรากฏใน เห็นได้ชัดว่าโครงสร้างข้อมูลนี้ต้องการพื้นที่จัดเก็บข้อมูลจำนวนคำ เนื่องจากดังที่กล่าวไว้ข้างต้น ในขั้นตอนการสร้างโหนดจะถูกทำเครื่องหมาย และสำหรับแต่ละโหนดที่ทำเครื่องหมายไว้ จะมีการจัดเก็บชุดตัวเลือกไว้ ตามคำจำกัดความ สำหรับแต่ละโหนดที่ทำเครื่องหมายไว้จะมีการจัดเก็บชุดตัวเลือกจำนวนหนึ่ง ซึ่งแต่ละชุดจะมีตัวเลือกอยู่ ดังนั้น โครงสร้างข้อมูลนี้จึงต้องการพื้นที่จัดเก็บข้อมูลจำนวนคำ โปรดทราบว่าแต่ละโหนดจะจัดเก็บค่าซึ่งเท่ากับจำนวนอินสแตนซ์ของบนเส้นทางจากไปยังรากของซึ่งจะไม่เพิ่มความซับซ้อนของพื้นที่จัดเก็บข้อมูล เนื่องจากจะเพิ่มเพียงจำนวนคำคงที่ต่อโหนดเท่านั้น ${\displaystyle 0\leq i\leq \log(depth(x))}$${\displaystyle \operatorname {par} (x)}$${\displaystyle x}$${\displaystyle P_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle (\tau /2)}$${\displaystyle P_{i}(x)}$${\displaystyle (\tau /2).(2^{i}+1)}$${\displaystyle P_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle 2/\tau }$${\displaystyle i}$${\displaystyle \tau }$${\displaystyle x}$${\displaystyle z}$${\displaystyle C_{i}(x)}$${\displaystyle P_{i}(x)}$${\displaystyle (2^{i}+1)}$${\displaystyle P_{i}(x)}$${\displaystyle 0\leq i\leq \log(depth(x))}$${\displaystyle d_{xz}{\text{ and }}2d_{xz}}$${\displaystyle d_{xz}}$${\displaystyle P_{i}(x)}$${\displaystyle \tau }$${\displaystyle x}$${\displaystyle z}$${\displaystyle (\tau /2)}$${\displaystyle P_{i}(x)}$${\displaystyle C_{i}(x)}$${\displaystyle O(n\log n)}$${\displaystyle O(\tau n)}$${\displaystyle O(\log n)}$${\displaystyle O(1/\tau )}$${\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}$${\displaystyle x}$${\displaystyle count(x)}$${\displaystyle label(x)}$${\displaystyle x}$${\displaystyle T}$

แต่ละคำถามระหว่างสองโหนดสามารถตอบได้โดยใช้คุณสมบัติการแยกส่วน (ตามที่อธิบายไว้ข้างต้น) ของคำถามแบบช่วงส่วนใหญ่ และโดยการแบ่งเส้นทางคำถามระหว่างและออกเป็นสี่เส้นทางย่อย ให้เป็นบรรพบุรุษร่วมที่ต่ำที่สุดของและโดยที่และเป็นบรรพบุรุษที่ทำเครื่องหมายไว้ใกล้ที่สุดของและตามลำดับ เส้นทางจากไปยังจะถูกแยกส่วนออกเป็นเส้นทางจากและไปยังและตามลำดับ (ขนาดของเส้นทางเหล่านี้เล็กกว่าตามคำจำกัดความ ซึ่งทั้งหมดถือเป็นผู้สมัคร) และเส้นทางจากและไปยัง(โดยการหาที่เหมาะสมตามที่อธิบายไว้ข้างต้นและพิจารณาป้ายกำกับทั้งหมดเป็นผู้สมัคร) โปรดทราบว่า โหนดขอบเขตจะต้องได้รับการจัดการอย่างเหมาะสมเพื่อให้เส้นทางย่อยทั้งหมดเหล่านี้ไม่ทับซ้อนกัน และจากทั้งหมดเหล่านี้จะได้รับชุดของผู้สมัคร ผู้สมัครแต่ละรายจะได้รับการตรวจสอบโดยใช้การรวมกันของคำถามที่ส่งคืนบรรพบุรุษที่ต่ำที่สุดของโหนดที่มีป้ายกำกับและฟิลด์ของแต่ละโหนด บนRAM ขนาด - บิตและตัวอักษรขนาดคำถามสามารถตอบได้ในเวลา ในขณะที่มีความต้องการพื้นที่เชิงเส้น^{[ 17 ]}ดังนั้น การตรวจสอบผู้สมัครแต่ละคนในเวลาที่เหมาะสมจะส่งผลให้เวลาในการสอบถามทั้งหมดสำหรับการส่งคืนชุดของเสียงข้างมากทั้งหมดบนเส้นทางจากไปยัง ${\displaystyle u}$${\displaystyle v}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$${\displaystyle z}$${\displaystyle u}$${\displaystyle v}$${\displaystyle x}$${\displaystyle y}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle x}$${\displaystyle y}$${\displaystyle 2\lceil 1/\tau \rceil }$${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle C_{i}(x)}$${\displaystyle O(1/\tau )}$${\displaystyle labelanc(x,\ell )}$${\displaystyle x}$${\displaystyle \ell }$${\displaystyle count(x)}$${\displaystyle w}$${\displaystyle \sigma }$${\displaystyle labelanc(x,\ell )}$${\displaystyle O\left(\log \log _{w}\sigma \right)}$${\displaystyle O(1/\tau )}$${\displaystyle O\left(\log \log _{w}\sigma \right)}$${\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}$${\displaystyle \tau }$${\displaystyle u}$${\displaystyle v}$

ปัญหาทั้งหมดที่อธิบายไว้ข้างต้นได้รับการศึกษาสำหรับมิติที่สูงขึ้นรวมถึงเวอร์ชันไดนามิกด้วย ในทางกลับกัน การค้นหาช่วงอาจขยายไปยังโครงสร้างข้อมูลอื่น ๆ เช่นต้นไม้[ ^{8 ] เช่น}ปัญหาบรรพบุรุษระดับปัญหาที่คล้ายกันอีกประเภทหนึ่งคือ การค้นหา ช่วงแบบตั้งฉากหรือที่รู้จักกันในชื่อการค้นหาการนับ

• ปัญหาบรรพบุรุษระดับ
• บรรพบุรุษร่วมที่ต่ำที่สุด

• โครงสร้างข้อมูลแบบเปิด - บทที่ 13 - โครงสร้างข้อมูลสำหรับจำนวนเต็ม
• โครงสร้างข้อมูลสำหรับการสืบค้นค่ามัธยฐานช่วง - Gerth Stolting Brodal และ Allan Gronlund Jorgensen