http://www.spoj.com/problems/RANGESUM/
For solving this you need to know how to use segment trees for finding the sum of a given range in O(logN) time. For learning the segment trees go here. So, we keep an array which represents our tree of length of a number bigger than N which is a power of two. First of all we will increase that size, we will have the size which is a power of 2 and bigger than 2*N so that we can have more "free" leaves. (In our case free means that it has a value of 0). We will fill our array starting from the leftmost leaf (a leaf which has a smaller index) in reverse order so that whenever we will have to add an element to the beginning of the array we can use the "free" leaves for that. Then the rest is a simple segment tree implementation. Check the source code for a better understanding.
For solving this you need to know how to use segment trees for finding the sum of a given range in O(logN) time. For learning the segment trees go here. So, we keep an array which represents our tree of length of a number bigger than N which is a power of two. First of all we will increase that size, we will have the size which is a power of 2 and bigger than 2*N so that we can have more "free" leaves. (In our case free means that it has a value of 0). We will fill our array starting from the leftmost leaf (a leaf which has a smaller index) in reverse order so that whenever we will have to add an element to the beginning of the array we can use the "free" leaves for that. Then the rest is a simple segment tree implementation. Check the source code for a better understanding.
download link not working
ReplyDeleteHI
ReplyDeleteThe links works perfectly. When you open it a little ad page pops up which takes only 5 seconds to go, after those 5 second you need to click "skip this ad" and you will be on the code page.