Any easy way for Count numbers in a range : Segment Tree , Lazy

general
, ,
1

given A[1…N] and K two types of query :

type-1 : count number in range [L R] such that A[i] >= K.

type-2 : given no X and range [L R], add value x to all numbers in given range A[i] += X .

1 <= N ,Q <= 10 ^ 5 [ no of elements and no of queries ]

-10^9 <= A[i] ,X <= 10^9 [X is different for each query]

-10^18 <= K <= 10^18

1 <= L <= R <= N

EX :

5 6 2 [N Q K]

1 -2 3 -4 5 [Array A]

1 2 4 [type L R ]

1 3 5

2 1 4 2 [type L R X]

1 1 5

2 1 4 -1

1 1 3

Output :

1

2

3

2

Observation : K is same for all query type -1

Expected Runtime : O(N * logQ)

I was trying such a standard problem , Any possible segment-tree,lazy solution O(N * logQ) so it will be also useful in Tree-path HLD problems O(Q * log N * log N)

Thanks in Advance.

2 Likes
2

Nice problem :slight_smile:
this problem can be easily solved using square root decomposition method.

We can divide the initial n numbers into B buckets, sort the number in each buckets and maintain the total add val in each bucket. Then for each query:

“Add” update interval [a, b] with c

we only need to rebuild at most two buckets and add c to (b - a) / BUCKET_SIZE buckets

“Query” query interval [a, b] >= c

we only need to scan at most two buckets with each value one by one and quick go through (b-a) / BUCKET_SIZE buckets with binary search quickly

It should be run in O( N/BUCKET_SIZE * log(BUCKET_SIZE, 2)) for each query, which is smaller than bruteforce method( O(N)). Though it’s bigger than O(logN), it may be sufficient in most cases.

5 Likes
3

it depends on the problem like is where to be use -:

  1. if you want to find number of elements for more than one ranges than i’ll suggest that use any sorting technique.

exp : suppose you want find no of elements for ranges :- [a,b] [d,b] [c,d] etc

  1. if you want yo find only for one range than :-

    for(i=;i<n;i++)

{ if(array[i] >= a && array[i] <= b)

count++;
}

Hope i am right!

4

Sorry,I can solve this problem(only with sqrt(n)log(n) or log^2(n)),if you need this solution,please write me!

5

I am just explaining @yash_chauhan28 answer here.

Let the array be A =[1, 4, 3, 5, 2, 7, 4, 9, 8]. Divide it into segments of size BUCKET_SIZE (say ROOT(N)).

then, it will look like A = [1, 4, 3] [5, 2, 7] [4, 9, 8]. Then sort each segment separately and stor these somewhere else, DO NOT modify the array A.
for this purpose lets say we created a list of vectors B = [1, 3, 4] [2, 5, 7] [4, 9, 8]

For update query, say, add 4 from 2 to 8 (1-based indexing). Do naive updation on array A for range which partially overlap with buckets, these are the elements which lies at the extremes of the update range, and then again sort these effected buckets and update vector list B. There can be at most two effected buckets.

For segments which lies completely inside update range, just add value 4 to their lazy term.

In our example, after updation array A would be = [1, 7, 8] [2, 5, 7] [8, 13, 8]

                        4  --- lazy term of segment 2

and B = [1, 7, 8] [2, 5, 7] [8, 8, 13]

We just needed to sort two segments of size ROOT(N), time = O(ROOT(N) * log N)

also we needed to add value 4 to the middle segments which can be at most ROOT(N)

Total update time = O(ROOT(N) + ROOT(N) * LogN) = *O(ROOT(N)LogN)

Query is straight forward. Naively count the elements of array A from the extreme which partially overlaps with query range.
For middle O(ROOT(N)) segments do a binary search for k + lazy(segment), in vector list B. Time = O(ROOT(N) * LogN)

Thus each query is answered in O(ROOT(N) * LogN)

For O(Log^2(N)) solution which @glebodin proposed, you can read rachitjain’s answer on this link.

There is also a Log(N) per each query solution explained at the last in that link.

6

@yash_chauhan28, please you explain your approach using code.

7

As i mentioned it will be also useful in Tree-path HLD problems O(Q * log N * log N) if each above query can be answered in O(log n)

8

It’s(sqrt(n)*log(n))(yash_chauhan28’s solution)! The log^2(n) solution is let make a segment tree with sorted subarray from l to r! Then let’s do a bin.search(the amount of elements>=k+x)!
It will be work: nlog(n)- memory, qlogn+nlogn time

9

@joney_000, can u provide link to this problem, so that I can try.

11

I tried this way implementing segment tree —but don’t know whether it is efficient or not

package competition;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

class Node
{
Node lptr;
Node rptr;
private Map<Integer, Integer> map;
int l;
int h;
public Node getLptr() {
return lptr;
}
public void setLptr(Node lptr) {
this.lptr = lptr;
}
public Node getRptr() {
return rptr;
}
public void setRptr(Node rptr) {
this.rptr = rptr;
}
public Map<Integer, Integer> getMap() {
return map;
}
public void setMap(Map<Integer, Integer> map) {
this.map = map;
}

}

public class Solution {

public static void main(String[] args) {
	
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int arr[]=new int[n+1];
	for(int i=1;i<=n;i++)
	{
		arr[i]=sc.nextInt();
	}
	Node node=createSegmentTree(arr,1,n);
	/*Map<Integer, Integer>map = node.map;
	 Set<Map.Entry<Integer,Integer>> s = map.entrySet(); 
	 for (Map.Entry<Integer, Integer> it: s) 
        {
          System.out.println(it.getKey()+" "+it.getValue());		 
        }*/
	 
	//visitSegmentTree(node);
	Map<Integer, Integer>map2 = searchQuery(arr,node,0,0);
	 Set<Map.Entry<Integer,Integer>> s1 = map2.entrySet(); 
	 for (Map.Entry<Integer, Integer> it: s1) 
        {
          System.out.println(it.getKey()+" "+it.getValue());		 
        }
}
static Node createSegmentTree(int arr[],int l,int h)
{
	Node node1 = null ,node2=null;
	int mid;
	
	
	if (l == h)
	{
		Node node = new Node();
		Map<Integer, Integer> map = new HashMap<Integer,Integer>();
		map.put(arr[l], 1);
		node.setMap(map);
		node.l=l;
		node.h=h;
		return node;
	}
	else
	{
		mid = (l+h)/2;
		node1 = createSegmentTree(arr,l,mid);
		node2 = createSegmentTree(arr,mid+1,h);
		Map<Integer,Integer>map1 = node1.getMap();
		Map<Integer,Integer>map2 = node2.getMap();
		/*System.out.println("nod1 map before maerge:"+node1.getMap());
		System.out.println("nod2 map before merge:"+node2.getMap());
		map2.forEach( 
		        (key, value) 
		            -> map1.merge( 
		                key, 
		                value, 
		                (v1, v2) 
		                    -> v1  + v2)); 
		System.out.println("nod1 map after maerge:"+node1.getMap());
		System.out.println("nod2 map after merge:"+node2.getMap());*/
		Node node = new Node();
		Set<Integer>set1=map1.keySet();
		Set<Integer>set2=map2.keySet();
		
		Map<Integer,Integer>map3=new HashMap<Integer,Integer>();
		Iterator<Integer>iterator=set1.iterator();
		while(iterator.hasNext())
		{
			int key = iterator.next();
			if (map2.containsKey(key))
			{
				map3.put(key, map1.get(key)+map2.get(key));
			}
			else
			{
				map3.put(key, map1.get(key));
			}
			
		}
		iterator=set2.iterator();
		while(iterator.hasNext())
		{
			int key = iterator.next();
			if (!map3.containsKey(key))
			{
				map3.put(key, map2.get(key));
			}
		}
		
		node.lptr=node1;
		node.rptr =node2;
		node.setMap(map3);
		node.l=l;
		node.h=h;
		return node;
	}
}

static Map<Integer, Integer> searchQuery(int[] a,Node node,int q1,int q2)
{
	
	int mid = 0;
	if(q1 == node.l && q2 == node.h)
	{
		Map<Integer, Integer>map = node.getMap();
		return map;
	}
	else
	{
		mid = (node.l+node.h) / 2;
		if (q1<=mid && mid<q2)
		{
			Map<Integer, Integer>map1 = searchQuery(a,node.lptr,q1,mid);
			Map<Integer, Integer>map2 = searchQuery(a,node.rptr,mid+1,q2);
			map2.forEach( 
			        (key, value) 
			            -> map1.merge( 
			                key, 
			                value, 
			                (v1, v2) 
			                    -> v1  + v2));
			return map1;
		}
		else if(q1>mid && mid<q2 )
		{
			Map<Integer, Integer>map1 = searchQuery(a,node.rptr,q1,q2);
			return map1;
		}
		else 
		{
			Map<Integer, Integer>map1 = searchQuery(a,node.lptr,q1,q2);
			return map1;
		}
		
		
	}
	
	
}
static int min(int num1,int num2)
{
	if(num1<num2)
	{
		return num1;
	}
	else
	{
		return num2;
	}
}

static void visitSegmentTree(Node node)
{
	
   if(node.l == node.h)
   {
	   System.out.println(node.l+" "+node.h);
	   System.out.println(node.getMap());
	   System.out.println("============");
   }
   else
   {
	   visitSegmentTree(node.lptr);
	   visitSegmentTree(node.rptr);
	   System.out.println(node.l+" "+node.h);
	   System.out.println(node.getMap());
	   System.out.println("============");
   }
}

}