Stack Overflow
Stack Overflow

Questions tagged [segment-tree]

A segment tree is a heap-like data structure that can be used for making update/query operations upon array intervals in logarithmical time.

A segment tree is a balanced tree where each node corresponds to an interval. The leaves correspond to the atomic intervals according to left to right order. An internal node u corresponds to the union of the intervals corresponding to the leaves of the subtree rooted at u.

A segment tree for a set of n intervals can be constructed in O(nlogn) time.

A d-dimensional segment tree for a set of n axis-aligned rectangular boxes in R d can be built in O(n(logn)^ d ) time and takes O(n(logn)^ d ) space.

273 questions
241
votes
3 answers

What are the differences between segment trees, interval trees, binary indexed trees and range trees?

What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of: Key idea/definition Applications Performance/order in higher dimensions/space consumption Please do not just give definitions.
Aditya
  • 5,509
  • 4
  • 31
  • 51
30
votes
4 answers

Fenwick tree vs Segment tree

I needed to compute sums within a range on an array, so I came across Segment Tree and Fenwick Tree and I noticed that both of these trees query and update with the same asymptotic running time. I did a bit more research, and these 2 data structures…
Will Kanga
  • 652
  • 1
  • 6
  • 12
30
votes
7 answers

How is the memory of the array of segment tree 2 * 2 ^(ceil(log(n))) - 1?

The link: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/. This is the quoted text: We start with a segment arr[0 . . . n-1]. And every time we divide the current segment into two halves(if it has not yet become a segment of…
dauntless
  • 413
  • 1
  • 4
  • 6
23
votes
5 answers

Is it possible to query number of distinct integers in a range in O(lg N)?

I have read through some tutorials about two common data structure which can achieve range update and query in O(lg N): Segment tree and Binary Indexed Tree (BIT / Fenwick Tree). Most of the examples I have found is about some associative and…
shole
  • 4,046
  • 2
  • 29
  • 69
14
votes
4 answers

Segment tree java implementation

Do you know a good implementation of a (binary) segment tree in Java?
talg
  • 1,759
  • 6
  • 22
  • 30
14
votes
2 answers

data mapping and lazy propagation in segment tree

Looks like there is only one good article about lazy propagation in Segment Tree on entire internet and it is: http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296 I understood the concept of updating only query node and marking its child. But my…
Pranalee
  • 3,389
  • 3
  • 22
  • 36
13
votes
2 answers

Find the largest sum subarray from the given array using segment trees

I wanted to find the largest sum continuous subarray from the given array. I know the O(n) approach of finding the largest sum continuous subarray approach using the concept of dynamic programming using Kadane's algorithm. But it will take a lot of…
user1580096
  • 487
  • 1
  • 7
  • 17
10
votes
5 answers

Segment tree time complexity analysis

How can we prove that the update and query operations on a segment tree (http://letuskode.blogspot.in/2013/01/segtrees.html) (not to be confused with an interval tree) are O(log n)? I thought of a way which goes like this - At every node, we make at…
adijo
  • 1,450
  • 1
  • 14
  • 20
9
votes
3 answers

CSES Range Query Question: Salary Queries

I'm trying to solve this problem: https://cses.fi/problemset/task/1144/ Given an array of up to 200000 elements, my task is to process up to 200000 queries, which either ask me to update a single value within the array or ask me to find the number…
Christopher Miller
  • 861
  • 4
  • 9
9
votes
3 answers

Update in Segment Tree

I am learning segment tree , i came across this question. There are Array A and 2 type of operation 1. Find the Sum in Range L to R 2. Update the Element in Range L to R by Value X. Update should be like this A[L] = 1*X; A[L+1] = 2*X; A[L+2] =…
DreamWorks
  • 174
  • 7
9
votes
2 answers

STL for segment tree in C++

Is there any STL for segment tree? In competitive programming it takes a lot of time to code for seg tree. I wonder if there is any STL for that so that lot of time could be saved.
Ankita Singh
  • 107
  • 1
  • 5
8
votes
2 answers

Fitting a segment in a two-dimensional plane

I'm having troubles with the following problem Given N x S grid and m segments parallel to the horizontal axis (all of them are tuples (x', x'', y)), answer Q online queries of form (x', x''). The answer to such a query is the smallest y (if there…
Y N
  • 811
  • 1
  • 6
  • 22
8
votes
2 answers

Segment tree implementation in Python

I am solving this problem using segment tree but I get time limit error. Below is my raw code for range minimum query and by changing min to max in my code the above problem can be solved . I don't know how I can improve the performance of my code.…
sid597
  • 999
  • 3
  • 16
  • 31
8
votes
2 answers

Segment tree space requirement

I have found as explained in this article on HackerEarth that segment trees can be implemented by using arrays where child elements of a node positioned at array-index n are at indexes 2n and 2n+1. Also it states that for storing n elements in my…
brijs
  • 525
  • 6
  • 18
7
votes
1 answer

Range Query the number of inversion in O(lg N)

Given an unsorted array of n integers, I know I can find the total number of inversions using BIT in O(N lg N)following this method: Count Inversion by BIT However is it possible if I have to query an arbitrary range for the total # of inversions in…
shole
  • 4,046
  • 2
  • 29
  • 69
1
2 3
…
18 19