線段樹 (儲存區間) 線段樹英語Segment tree是一種二元樹形資料結構年由喬恩本特利發明用以儲存區間或線段並且允許快速查詢結構內包含某一點的所有區間 一個包含 n displaystyle n 個區間的線段樹空間複雜度為 O  n  displaystyle On 查詢的時間複雜度則為 O  log  n  k  displaystyle Olog nk 其中 k displaystyle k 是符合條件的區間數量 此資料結構亦可推廣到高維度