Help with segment trees - query processing

general
, , ,
1

Hello all,

I am now attempting to solve the problem FLIPCOIN in the practice section, medium difficulty level.

I am aware that a naive solution gets TLE… However, I also know that some sort of segment tree data structure can and needs to be used to process queries fast.

Below is my naive and wrong (from the execution time point of view) code, that gives me a TLE:

#include <stdio.h>

int main()
{
	int N,Q;
	int i;
	scanf("%d %d", &N, &Q);
	char* array;
	array = (char *)malloc(N*sizeof(char));
	for(i = 0; i < N; i++)
	{
		array[i] = 'T';
	}
	int q;
	for(q = 0; q < Q;q++)
	{
		int control,low,high;
		scanf("%d %d %d", &control,&low,&high);
		if(control == 0)
		{
			for(i=low;i <= high; i++)
			{
				if(array[i] == 'T')
				array[i] = 'H';
				else
				array[i] = 'T';
			}
		}
		else
		{
			int auxiliar = 0;
			for(i=low;i <= high; i++)
			{
				if(array[i] == 'H')
				auxiliar++;
			}
			printf("%d\n", auxiliar);
		}
	}
	return 0;
}

What I would like to ask, if that is possible is either a very good and explanatory reference with examples to implement segment trees for a similar problem, or, something that would be even better, if someone with more expertise could provide some sort of “editorial” and provide me with tips along the way, so that I could implement a segment tree on my own, I would be very appreciated.

The reason why I ask this is that sometimes, even after reading editorials I have some trouble implementing some new data structures and a more guided and step by step explanation would help me a lot… If I can do simple things, one at a time and end up with a segment tree implemented and understood on my own, i’d be very, very thankful :smiley:

Thanks in advance,

Bruno

2

There very similar question to yours - http://discuss.codechef.com/questions/2068/flip-coins-solutions-arent-public . And probably the answer is exactly what you are looking for…

Especially this sample problem is the same one.

If there is still problem we can elaborate more :wink:

3

Hello @betlista,

Thanks for your response, but I’d actually prefer a more naive explanation (like if I was 5 y.o. really!) of this concept…

Because, like graphs, sometimes I get a bit lost in the theory behind the concepts and totally fail at implementing them…

So, several things:

  • Using trees, queries can be processed in O(logN) time;
  • They provide the only fastest way to get AC to these sort of problems;
  • They can be implemented using either arrays or heaps/binary trees (I think);
  • They depend upon the range of the queries, i.e., if it’s either updating 1 element, or several;

If I want to write an efficient method to query over an array, something with a signature like:

int query(int low, int high)

where this function will return me (for this problem) the number of coins heads up between low and high, I will need a method update, like:

void update(int low, int high)

My questions are:

What auxiliary data structures do I need to use/create,besides a tree, so that I can use these methods efficiently?

How to create a tree in itself?

For example, if our input array was called simply array, we know that, initially we have:

array[N] = {'T', 'T',..., 'T'};

would this function for querying values be correct:

int query(int low, int high)
{
    int auxiliar = 0;
    for(i=low;i <= high; i++)
    {
    	if(array[i] == 'H')
    	auxiliar++;
        }
        return auxiliar;
   }

This is where I’ve come so far… Any help would be extremely useful, thanks in advance,

Bruno

1 Like
4

no!!I dont think above query function is right!!It would take a lot time!!Instead of use Segment trees…Just subtract the no of heads coins from total no of coins below that node!!And just use some basic function on query and update!I guess this might help for reference

5

I really dont know much about data structs but i found my own way of solving such probs.
I simply create two arrays, one for each element stored individually and other which stores result of 100 element in one block. While processing queries i use those those groups to make my program around 100 times faster to get AC :slight_smile:

Here is a link to my soln.

6

You can read a very nice tutorial on segment trees here

1 Like
7

I wrote a tutorial about Lazy Updates. Let me know if you have any more questions.
Good luck!