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 exampl...

I'm implementing segment tree from an array of data, and I also want to maintaining the max/min of the tree while updating a range of data. Here is my initial approach following this tutorial http:...

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...

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 int...

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 sho...

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 consu...

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 ...

I am having problems with understanding segment tree complexity. It is clear that if you have update function which has to change only one node, its complexity will be log(n). But I have no idea wh...

I know that this problem can be solved using modified merge sort and I have coded same. Now I want to solve this problem using Segment Tree. Basically, if we traverse from right to left array then ...

I found that many people use x += x & (-x), x -= x & (-x) to solve the interval tree problem (While implementing data structures like segment tree, binary indexed tree etc). Can you explain...

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 v...

I've been thinking a lot about the following problem: We are given an array of n numbers. We start at the first index and our task is to get to the last index. Every move we can jump one or two st...

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''). T...

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 ...

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...

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....

Do you know a good implementation of a (binary) segment tree in Java?

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 quer...

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.

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 up...