Questions tagged [segment-trees]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-1 votes
2 answers

Given m intervals and an array of integers, your task is to minimize the number of operations in which you can make the elements of the array nonposit

You are given the number $m$ and $m$ intervals of the form $a_i, b_i, v_i$, where $a_i<=b_i$ and $v_i>0$ and also a number $n$ and an array $s$ of length $n$, where $s_i>0$. In one operation ...
John's user avatar
  • 1
-3 votes
1 answer

Can you simulate the following process in $O(N.log N)$

Given an array $A[]$ of N integers. pseudocode: Traverse from left to right of this array. Let's say you are standing at index $j$. For each index i=1 to i=j-1, increment all $A[i]$ by $1$ if and ...
sibillalazzerini's user avatar
0 votes
0 answers

Zero sequence query in boolean array

I have a large array of bits of length $N$. The query $f(k, m)$ means "find $kth$ zero in the array and the next $m-1$ zeros after it", $k \in [0, N-1], m \ll N$ Currently I use a segment ...
Andrey Godyaev's user avatar
1 vote
1 answer

Find the largest segment within a queried range?

We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$. Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$. ...
ishandutta2007's user avatar
3 votes
1 answer

Segment trees with insertion/deletion

I have a range-query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
matheuscscp's user avatar