Questions Tagged With suffixhttps://discuss.codechef.com/tags/suffix/?type=rssquestions tagged <span class="tag">suffix</span>enMon, 12 Nov 2018 17:29:55 +0530Doubt in triehttps://discuss.codechef.com/questions/11929/doubt-in-trie<p>can someone explain me,what is the difference between radix tree and suffix tree??</p>hariprasathThu, 30 May 2013 12:22:19 +0530https://discuss.codechef.com/questions/11929/doubt-in-trieradixsuffixWhat is wrong with the suffix array approachhttps://discuss.codechef.com/questions/21364/what-is-wrong-with-the-suffix-array-approach<p>I was solving this question <a href="https://www.hackerrank.com/contests/quantium/challenges/k-mismatch">https://www.hackerrank.com/contests/quantium/challenges/k-mismatch</a> but sometimes it gives me wrong answer. What is wrong with my approach?</p>
<p>I used suffix array and lcp array.</p>
<p>We know that any prefix of a suffix is a substring of the string itself, so after finding the suffix array and the lcp array I did the following:</p>
<p>I choose two suffixes say i & j, suppose suffix i smaller than j.</p>
<p>Their lcp(i, j) will tell me the number of chars in common until I hit a mismatch or the suffix ends.</p>
<p>if the suffix ends then we r done the number of accepted pairs is the lcp itself.
otherwise if the mismatch doesn’t exceed k then we add lcp(i, j) + 1 to the result, then I start again with new suffixes.</p>
<p>I’ll give an example to make it more clear:</p>
<p>suffix i: abcdef
suffix j: abceeeefff
suppose k is 1</p>
<p>lcp(i, j) = 3 & the first mismatch is d & e. this mismatch doesn’t exceed k so res += (3 + 1) then new suffixes are:</p>
<p>suffix i: ef
suffix j: eeefff</p>
<p>Notice how I removed the lcp and the mismatch.</p>
<p>now lcp(i, j) = 1 & mismatch is f & e but the mismatch will now exceed k so we just count lcp thus res += 1 which yields res = 5</p>
<p>Here is a function that finds solution for i & j;</p>
<p>LL solve(int i, int j, int n, int k) {</p>
<p>int x = n - pos[i]; // Length of suffix i </p>
<p>int y = n - pos[j]; // Length of suffix j</p>
<p>// Put shorter suffix in x and longer in y
if(x > y) swap(x, y), swap(i, j);
LL ret = 0, m = 0;</p>
<p>while(x > 0) {
ret += lcp1[i][j];</p>
<pre><code>// if all suffix i is a match break otherwise we have a mismatch
if(x == lcp1[i][j]) break;
// if this mismatch excceeds k then break otherwise count it
if((m + 1) > k) break;
m++;
// remove the matched chars and mismatched char
x -= (lcp1[i][j] + 1);
y -= (lcp1[i][j] + 1);
// update the position of the new suffixes in the suffix array.
// rank returns the position of suffix starting at position pos[i] + lcp1[i][j] + 1 in //the suffix array
i = rank[pos[i] + lcp1[i][j] + 1];
j = rank[pos[j] + lcp1[i][j] + 1];
</code></pre>
<p>}</p>
<p>return ret + m; // return matches + mismatches</p>
<p>}</p>bondoc73Fri, 16 Aug 2013 16:25:38 +0530https://discuss.codechef.com/questions/21364/what-is-wrong-with-the-suffix-array-approachsuffixsuffix-arrayImplementing suffix arrayhttps://discuss.codechef.com/questions/54183/implementing-suffix-array<p>Given a string S[1....n] and l where l is an integer less than n then how can we efficiently construct the function f(n) (please see below for more explanation)
for every string S[i,j] where
j-i=l</p>
<p>f(n) denotes the longest longest suffix which is also the prefix of a string. </p>japoorvSun, 26 Oct 2014 21:31:38 +0530https://discuss.codechef.com/questions/54183/implementing-suffix-arrayarraysuffixJava :Alternative to lambda expressionhttps://discuss.codechef.com/questions/63764/java-alternative-to-lambda-expression<p><a href="https://sites.google.com/site/indy256/algo/suffix_array2">https://sites.google.com/site/indy256/algo/suffix_array2</a></p>
<p>Can anyone provide me the alternative statement to the Arrays.sort line that should work with Java 7.
Thanks. :)</p>abeyaarTue, 03 Feb 2015 13:00:16 +0530https://discuss.codechef.com/questions/63764/java-alternative-to-lambda-expressionjavasuffixjava8java7alternativearraysuffix automationhttps://discuss.codechef.com/questions/70532/suffix-automation<p>can any one please explain Suffix automaton construction ? thanks in advance :)</p>rnagarjunaMon, 25 May 2015 11:45:48 +0530https://discuss.codechef.com/questions/70532/suffix-automationsuffixautomationsuffix automationhttps://discuss.codechef.com/questions/70531/suffix-automation<p>can any one please explain Suffix automaton construction ? thanks in advance :)</p>rnagarjunaMon, 25 May 2015 11:45:47 +0530https://discuss.codechef.com/questions/70531/suffix-automationsuffixautomationSuffix array and Suffix treehttps://discuss.codechef.com/questions/71191/suffix-array-and-suffix-tree<p>Can anyone tell me the simplest implementation of sufix tree and suffix array(nlogn^2).?</p>shivam9753Sun, 07 Jun 2015 18:55:44 +0530https://discuss.codechef.com/questions/71191/suffix-array-and-suffix-treesuffixsuffix arrayshttps://discuss.codechef.com/questions/70571/suffix-arrays<p>any one please explain how SA CONSTRUCTION WORKS in this link :<a href="https://ideone.com/8UVnhS">https://ideone.com/8UVnhS</a></p>rnagarjunaMon, 25 May 2015 23:03:12 +0530https://discuss.codechef.com/questions/70571/suffix-arraysarraysuffixgetting wrong answer on spoj SUBST1https://discuss.codechef.com/questions/70580/getting-wrong-answer-on-spoj-subst1<p>any one please help me what's wrong with my solution:<a href="https://ideone.com/fVhCSG">https://ideone.com/fVhCSG</a>
its giving WA running perfectly on my maching</p>rnagarjunaTue, 26 May 2015 10:56:05 +0530https://discuss.codechef.com/questions/70580/getting-wrong-answer-on-spoj-subst1arraysuffixsuffix arrayshttps://discuss.codechef.com/questions/70562/suffix-arrays<p>Can any one please explain me what is happening in the suffix array nlogn algorithm from line 59 to 89
I cant understand what is the significance of bh2,cnt arrays?
link:<a href="https://ideone.com/fjbYBr">https://ideone.com/fjbYBr</a></p>rnagarjunaMon, 25 May 2015 19:28:51 +0530https://discuss.codechef.com/questions/70562/suffix-arraysarraysuffixHelp in suffix tree implementation(WA)https://discuss.codechef.com/questions/121686/help-in-suffix-tree-implementationwa<p>code : <a href="https://ideone.com/ZUfpWX">https://ideone.com/ZUfpWX</a></p>
<p>prob : <a href="https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/tutorial/">https://www.hackerearth.com/practice/data-structures/advanced-data-structures/suffix-trees/tutorial/</a> (practice prob).</p>
<p>I am getting wrong answer for last 2(UPD : 3days lol) days. Didn't able to find the bug! please help.</p>
<p>In simple words Ques just asked to sort all the suffix and print at which index suffix with sortedIndex 'j' starts!</p>
<p>My approach : i have just created a suffix tree and then just do a dfs on the tree and keep counts of number of indexes visited(end_Of_Curr_Node - start_Of_Curr_Node + 1) upto the current node. Now, as we reach leaf node(as we have inserted a unique '$' character so, all the suffixes must end in root) we have the count of the number of indices visited and to get the index of the suffix in the original string we just subtract it by lenghtOfString. </p>
<p>Why I think that this is correct? : I start doing dfs from '0' to '255' and so ensures that we visit each valid suffixes in lexographical order and so, the first reached leaf is the one which comes first when we sort all the substrings!</p>pk301Sat, 20 Jan 2018 00:26:25 +0530https://discuss.codechef.com/questions/121686/help-in-suffix-tree-implementationwahelp_pleasewasuffixSuffix treehttps://discuss.codechef.com/questions/123117/suffix-tree<p>hello guys,
i wanted to learn about suffix tree for implementing KILLKTH problem from jan long.
can anyone give refrences to good aticle or blog on suffix tree.
thanks</p>vikaskodag98Wed, 14 Feb 2018 22:29:53 +0530https://discuss.codechef.com/questions/123117/suffix-treetreesuffixA tutorial on Suffix Arrayshttps://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays<p>Hello <a href="/users/9989/allada">@all</a>,</p>
<p>This text will focus on the construction of Suffix Arrays, it will aim to explain what they are and what they are used for and hopefully some examples will be provided (it will be mainly simple applications so that the concepts don't get too attached to the theoretical explanation).</p>
<p>As usual, this follows my somewhat recent series of tutorials in order to make the reference post with links as complete as possible!</p>
<ul>
<li><strong>What is a Suffix Array?</strong></li>
</ul>
<p>In simple terms, a <strong>suffix array</strong> is just a sorted array of all the suffixes of a given string. </p>
<p>As a data structure, it is widely used in areas such as data compression, bioinformatics and, in general, in any area that deals with strings and string matching problems, so, as you can see, it is of great importance to know efficient algorithms to construct a suffix array for a given string.</p>
<p>Please note that on this context, the name <a href="http://en.wikipedia.org/wiki/Suffix_%28computer_science%29">suffix</a> is the exact same thing as substring, as you can see from the wikipedia link provided.</p>
<p>A suffix array will contain integers that represent the starting indexes of the all the suffixes of a given string, <strong>after</strong> the aforementioned suffixes are sorted.</p>
<p>On some applications of suffix arrays, it is common to paddle the string with a special character (like #, @ or $) that is <strong>not</strong> present on the alphabet that is being used to represent the string and, as such, it's considered to be smaller than all the other characters. (The reason why these special characters are used will hopefully be clearer ahead in this text)</p>
<p>And, as a picture it's worth more than a thousand words, below is a small scheme which represents the several suffixes of a string (on the left) along with the suffix array for the same string (on the right). The original string is <strong>attcatg$</strong>.</p>
<p><img alt="alt text" src="http://discuss.codechef.com/upfiles/suffix_arrays1_1.png"></p>
<p>The above picture describes what we want to do, and our goal with this text will be to explore different ways of doing this in the hope of obtaining a good solution.</p>
<p>We will enumerate some popular algorithms for this task and will actually implement some of them in C++ (as you will see, some of them are trivial to implement but can be too slow, while others have faster execution times at the cost of both implementation and memory complexity).</p>
<ul>
<li><strong>The naive algorithm</strong></li>
</ul>
<p>We shall begin our exploration of this very interesting topic by first studying the most naive algorithm available to solve our problem, which is also the most simple one to implement.</p>
<p>The key idea of the naive algorithm is using a <strong>good comparison-based sorting algorithm</strong> to sort all the suffixes of a given string in the fastest possible way. <strong>Quick-sort</strong> does this task very well. </p>
<p>However we should remind ourselves that we are sorting strings, so, either we use the <strong>overloaded < sign</strong> to serve as a "comparator" for strings (this is done internally in C++ for the string data type) or we write our own string comparison function, which is basically the same thing regarding time complexity, with the former alternative consuming us more time on the writing of code. As such, on my own implementation I chose to keep things simple and used the built-in sort() function applied to a vector of strings. As to compare two strings, we are forced to iterate over all its characters, the time complexity to compare strings is O(N), which means that:</p>
<p><strong>On the naive approach, we are sorting N strings with an O(N log N) comparison based sorting algorithm. As comparing strings takes O(N) time, we can conclude that the time complexity of our naive approach is O(N<sup>2</sup> log N)</strong></p>
<p>After sorting all the strings, we need to be able to "retrieve" the original index that each string had initially so we can actually build the suffix array itself.</p>
<p>[Sidenote: As written on the image, the indexes just "come along for the ride".</p>
<p>To do this, I simply used a map as an auxiliary data structure, such that the keys are the strings that will map to the values which are the original indexes the strings had on the original array. Now, retrieving these values is trivial.]</p>
<p>Below, you can find the code for the naive algorithm for constructing the <strong>Suffix Array</strong> of a given string entered by the user as input:</p>
<pre><code>//Naive algorithm for the construction of the suffix array of a given string
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
string s;
map<string,int> m;
cin >> s;
vector<string> v;
for(int i = 0; i < s.size();i++)
{
m[s.substr(i,s.size()-i)] = i;
v.push_back(s.substr(i,s.size()-i));
}
sort(v.begin(),v.end());
for(int i = 0; i < v.size();i++)
{
cout << m[v[i]] << endl;
}
return 0;
}
</code></pre>
<p>As you can see by the above code snippet, the implementation of the naive approach is pretty straightforward and very robust as little to virtually no space for errors is allowed if one uses built-in sorting functions.</p>
<p>However, such simplicity comes with an associated cost, and on this case, such cost is paid with a relatively high time complexity which is actually impractical for most problems. So, we need to tune up this approach a bit and attempt to devise a better algorithm.</p>
<p>This is what will be done on the next section.</p>
<ul>
<li><strong>A clever approach of building the Suffix Array of a given string</strong></li>
</ul>
<p>As noted above, <strong>Suffix Array construction</strong> is <strong>simple</strong>, but <strong>an efficient Suffix Array construction</strong> is <strong>hard</strong>.</p>
<p>However, after some thinking we can actually have a very defined idea of why we are performing so badly on such construction.</p>
<p>The reason why we are doing badly on the construction of the SA is because we are <strong>NOT EXPLOITING</strong> the fact that the strings we are sorting, are actually all part of the <strong>SAME</strong> original string, and not random, unrelated strings.</p>
<p>However, how can this observation help us?</p>
<p>This observation can help us greatly because now we can actually use tuples that contain only some characters of the string (which we will group in powers of two) such that we can sort the strings in a more ordered fashion by their first two characters, then we can improve on and sort them by their first four characters and so on, until we have reached a length such that we can be sure all the strings are themselves sorted. </p>
<p>With this observation at hand, we can actually cut down the execution time of our SA construction algorithm from O(N<sup>2</sup> log N) to O(N log<sup>2</sup> N).</p>
<p>Using the amazing work done by <a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta">@gamabunta</a></a></a></a>, I can provide his explanation of this approach, along with his pseudo-code and later improve a little bit upon it by actually providing an actual C++ implementation of this idea:</p>
<p><strong> <a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta">@gamabunta</a></a></a></a>'s work </strong></p>
<p>Let us consider the original array or suffixes, <b>sorted only according to the first 2 character</b>. If the first 2 character is the same, we consider that the strings have the same <b>sort index</b>.</p>
<pre>Sort-Index Suffix-Index
0 10: <b>i</b>
1 7: <b>ip</b>pi
2 1: <b>is</b>sissippi
2 4: <b>is</b>sippi
3 0: <b>mi</b>ssissippi
4 9: <b>pi</b>
5 8: <b>pp</b>i
6 3: <b>si</b>ssippi
6 6: <b>si</b>ppi
7 2: <b>ss</b>issippi
7 5: <b>ss</b>ippi
</pre>
<p>Now, we wish to use the above array, and <b>sort the suffixes according to their first 4 characters</b>. To achieve this, we can assign <b>2-tuples</b> to each string. The first value in the <b>2-tuple</b> is the <b>sort-index</b> of the respective suffix, from above. The second value in the <b>2-tuple</b> is the <b>sort-index</b> of the suffix that starts <b>2 positions later</b>, again from above.</p>
<p>If the length of the suffix is less than 2 characters, then we can keep the second value in the <b>2-tuple</b> as <b>-1</b>.</p>
<pre>Sort-Index Suffix-Index Suffix-Index
after first 2 chars
and 2-tuple assigned
0 10: <b>i</b> -1 (0, -1)
1 7: <b>ip</b>pi 9 (1, 4)
2 1: <b>is</b>sissippi 3 (2, 6)
2 4: <b>is</b>sippi 6 (2, 6)
3 0: <b>mi</b>ssissippi 2 (3, 7)
4 9: <b>pi</b> -1 (4, -1)
5 8: <b>pp</b>i 10 (5, 0)
6 3: <b>si</b>ssippi 5 (6, 7)
6 6: <b>si</b>ppi 8 (6, 5)
7 2: <b>ss</b>issippi 4 (7, 2)
7 5: <b>ss</b>ippi 7 (7, 1)
</pre>
<p>Now, we can call <b>quick-sort</b> and sort the suffixes according to their first 4 characters by using the <b>2-tuples</b> we constructed above! The result would be</p>
<pre>Sort-Index Suffix-Index
0 10: <b>i</b>
1 7: <b>ippi</b>
2 1: <b>issi</b>ssippi
2 4: <b>issi</b>ppi
3 0: <b>miss</b>issippi
4 9: <b>pi</b>
5 8: <b>ppi</b>
6 3: <b>siss</b>ippi
7 6: <b>sipp</b>i
8 2: <b>ssis</b>sippi
9 5: <b>ssip</b>pi
</pre>
<p>Similarly constructing the <b>2-tuples</b> and performing <b>quick-sort</b> again will give us suffixes sorted by their <b>first 8 characters</b>.</p>
<p>Thus, we can sort the suffixes by the following pseudo-code</p>
<pre>SortIndex[][] = { 0 }
for i = 0 to N-1
SortIndex[0][i] = order index of the character at A[i]
doneTill = 1
step = 1
while doneTill < N
L[] = { (0,0,0) } // Array of 3 tuples
for i = 0 to N-1
L[i] = ( SortIndex[step - 1][i],
SortIndex[step - 1][i + doneTill],
i
)
// We need to store the value of i to be able to retrieve the index
sort L
for i = 0 to N-1
SortIndex[step][L[i].thirdValue] =
SortIndex[step][L[i-1].thirdValue], if L[i] and L[i-1] have the same first and second values
i, otherwise
++step
doneTill *= 2
</pre>
<p>The above algorithm will find the Suffix Array in <b>O(N log<sup>2</sup> N)</b>.</p>
<p><strong>end of <a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta">@gamabunta</a></a></a></a>'s work </strong></p>
<p>Below you can find a C++ implementation of the above pseudo-code:</p>
<pre><code>#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 65536
#define MAXLG 17
char A[MAXN];
struct entry
{
int nr[2];
int p;
} L[MAXN];
int P[MAXLG][MAXN];
int N,i;
int stp, cnt;
int cmp(struct entry a, struct entry b)
{
return <a href="http://a.nr">a.nr</a>[0]==<a href="http://b.nr">b.nr</a>[0] ?(<a href="http://a.nr">a.nr</a>[1]<<a href="http://b.nr">b.nr</a>[1] ?1: 0): (<a href="http://a.nr">a.nr</a>[0]<<a href="http://b.nr">b.nr</a>[0] ?1: 0);
}
int main()
{
gets(A);
for(N=strlen(A), i = 0; i < N; i++)
P[0][i] = A[i] - 'a';
for(stp=1, cnt = 1; cnt < N; stp++, cnt *= 2)
{
for(i=0; i < N; i++)
{
L[i].nr[0]=P[stp- 1][i];
L[i].nr[1]=i +cnt <N? P[stp -1][i+ cnt]:-1;
L[i].p= i;
}
sort(L, L+N, cmp);
for(i=0; i < N; i++)
P[stp][L[i].p] =i> 0 && L[i].nr[0]==L[i-1].nr[0] && L[i].nr[1] == L[i- 1].nr[1] ? P[stp][L[i-1].p] : i;
}
return 0;
}
</code></pre>
<p>This concludes the explanation of a more efficient approach on building the suffix array for a given string. The runtime is, as said above, <b>O(N log<sup>2</sup> N)</b>.</p>
<ul>
<li><strong>Constructing (and explaining) the LCP array</strong></li>
</ul>
<p>The LCP array (Longest Common Prefix) is an auxiliary data structure to the suffix array. It stores the lengths of the longest common prefixes between pairs of consecutive suffixes in the suffix array.</p>
<p>So, if one has built the Suffix Array, it's relatively simple to actually build the LCP array.</p>
<p>In fact, using once again <a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta"><a href="/users/387/gamabunta">@gamabunta</a></a></a></a>'s amazing work, below there is the pseudo-code which allows one to efficiently find the LCP array:</p>
<p>We can use the <b>SortIndex</b> array we constructed above to find the <b>Longest Common Prefix</b>, between any two prefixes.</p>
<pre>FindLCP (x, y)
answer = 0
for k = ceil(log N) to 0
if SortIndex[k][x] = SortIndex[k][y]
// sort-index is same if the first k characters are same
answer += 2<sup>k</sup>
// now we wish to find the characters that are same in the remaining strings
x += 2<sup>k</sup>
y += 2<sup>k</sup>
</pre>
<p>The <b>LCP Array</b> is the array of <b>Longest Common Prefixes</b> between the <b>i<sup>th</sup></b> suffix and the <b>(i-1)<sup>th</sup></b> suffix in the Suffix Array. The above algorithm needs to be called <b>N</b> times to build the <b>LCP Array</b> in a total of <b>O(N log N)</b> time.</p>
<ul>
<li><strong>Moving on from here</strong></li>
</ul>
<p>This post was actually the first long post I wrote about a subject which I'm not familiar with, <strong>AT ALL</strong>. This is always a risk I am also taking, but I tried to adhere only to the sub-topics I considered I mastered relatively well myself (at least, in theory, as I still don't think I could implement this correctly on a live contest or even a pratice problem... But, as I said many times, I'm here to work as hard as I can to learn as much as I can!)</p>
<p>I hope that what I wrote is, at least, decent and I did it basically as a good way of gathering information which is very spread over many papers and websites online, so that when people read this post they will be able to grasp the ideas for the naive solution as well as for the improvement presented as a better solution.</p>
<p>There are many interesting linear algorithms to "attack" this problem, with one of the most famous being the <a href="http://www.cs.umd.edu/class/fall2011/cmsc858s/SuffixArrays.pdf">Skew Algorithm</a>, which is lovely described on the link I provide here.</p>
<p>Besides this, there are several other algorithms which are also linear that exploit the relationship between Suffix Trees and the Suffix Array and that use linear sorting algorithm like radix sort, but, which I sadly don't yet understand which makes me unable to discuss them here.</p>
<p>However, I hope this little text does its job by at least gathering some useful information on a single post :) </p>
<p>I am also learning as I write these texts and this has helped me a lot on my evolution as a coder and I hope I can keep contributing to give all my best to this incredible cmmunity :D</p>
<p>Best regards,</p>
<p>Bruno Oliveira</p>kurumaSat, 17 Aug 2013 05:33:01 +0530https://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arraysarrayconstructionsuffixtutorialAppy Loves One ( HMAPPY1 ) Video Editorialhttps://discuss.codechef.com/questions/140110/appy-loves-one-hmappy1-video-editorial<p><a href="https://www.codechef.com/NOV18B/problems/HMAPPY1">Question</a></p>
<p><a href="https://www.youtube.com/watch?v=T47EFVOJbgc">Video Editorial</a></p>
<p><a href="https://www.youtube.com/watch?v=T47EFVOJbgc">https://www.youtube.com/watch?v=T47EFVOJbgc</a></p>cenation092Mon, 12 Nov 2018 17:29:55 +0530https://discuss.codechef.com/questions/140110/appy-loves-one-hmappy1-video-editorialprefixsuffixlongeditorialNPLFLC - Editorialhttps://discuss.codechef.com/questions/87263/nplflc-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/NPLFLC">Practice</a><br>
<a href="https://www.codechef.com/NPLQ1602/problems/NPLFLC">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/aniket20">Aniket Marlapalle</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/begin_hs">Harsh Shah</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/aniket20">Aniket Marlapalle</a></p>
<h1>DIFFICULTY:</h1>
<p>easy</p>
<h1>PREREQUISITES:</h1>
<p>binary indexed trees, binary search</p>
<h1>PROBLEM:</h1>
<p>You have an array of n numbers. You need to perform q queries of following type:<br>
</p><ul>
<li>Change the value at <b>x<sup>th</sup></b> index to <b>Y</b></li>
<li>Find if there is a suffix with sum equal to some given value <b>Y</b></li>
</ul> <p></p>
<h1>EXPLANATION:</h1>
<p></p><p>
Brute-force : For every query of the first type just update the value in the array. For every second query iterate from the end of the array to see if the suffix sum is equal to some given value.<br><br></p>
<p>Now we can see that the suffix sums if ordered from right to left follow the non-decreasing order. So we can use <b>binary search</b> to speed up the calculations. Do a binary search on the length of the suffix and check the sum of the suffix corresponding to this length, if it is greater that the required sum then check on lower lengths else continue the search on higher lengths.<br>
<br>
Now the only thing required is to find and update all the prefix sums. For this we can consider the reverse array and use <b>Binary indexed trees</b> or <b>segment trees</b> to update the array values and find the suffix sum faster.<br>
<br></p>
<p><b>Time Complexity</b> : $O(N*log(N) + Q*log(N)*log(N))$ <br>
First creation of BIT takes $O(log(N))$ time for each element. For every query binary search takes $O(log(N))$ steps and every BIT query is $O(log(N))$.</p>
<p></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://ideone.com/e2GJrZ">here</a> <br></p>aniket20Wed, 09 Nov 2016 22:36:41 +0530https://discuss.codechef.com/questions/87263/nplflc-editorialbinary-searchsuffixnplflcfenwick-treenplq1602segment-tree