0

I have to search the sum of numbers between range [3,5] after building a segment tree. For construction of tree I am executing the following code

public static void main(String[] args) {
        int arr[] = { 1, 3, 5, 7, 9, 11 };
        int n = arr.length;
        int tree[] = new int[2 * n];
        buildtree(arr, tree, 1, 0, n - 1); // index starts from 1
        Arrays.toString(tree).toString();
    }

    static int buildtree(int arr[], int tree[], int index, int ts, int te) {
        if (ts == te) {
            tree[index] = arr[ts];
            return arr[ts];
        }

        int mid = (ts + te) / 2;
        tree[index] = buildtree(arr, tree, (2 * index), ts, mid) + buildtree(arr, tree, ((2 * index) + 1), mid + 1, te);
        return tree[index];
    }

I get an exception array index out of bound while storing value for [3,3] . where am i going wrong?

Pri_stack
  • 187
  • 9
  • *Unrelated:* What do you believe `Arrays.toString(tree).toString()` does, and why do you believe that? – Andreas Aug 31 '20 at 07:06
  • The array needs to be 2 larger, i.e. `int[] tree = new int[2 * n + 2]` – Andreas Aug 31 '20 at 07:09
  • Why to you believe that calling `toString()` , which **returns** a string value, will print that string value? To print something, you need to call `print()`, as shown in any "Hello World" tutorial for console programs ever created. I highly recomment to you go through such a tutorial, to learn how to print from Java. – Andreas Aug 31 '20 at 07:11
  • Ohh I get it now..i missed the SOP part. But my main concern was ArrayIndexOutOfBound. In many tutorials i have seen the tree size is initialized to (2n) of the original array. is there any specific reason you suggested (2n+2) ? – Pri_stack Aug 31 '20 at 07:14
  • I take that back, it not the right solution. I suggest you simply create the arrays oversized, so you don't get the error, then **DEBUG** your code to see how the array is built up, and learn where your logic goes wrong. I don't actually know what the resultant array should be. --- [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) – Andreas Aug 31 '20 at 07:24
  • I found this height = (int)(Math.ceil(Math.log(size) / Math.log(2))); maxsize = 2 * (int) Math.pow(2, height) - 1; tree = new int[maxsize]; the array size is calculated depending upon the height of the tree. this seems to be a bit useful – Pri_stack Aug 31 '20 at 07:39
  • `(int) Math.pow(2, height)` is better written as `(1 << height)` – Andreas Aug 31 '20 at 10:00

0 Answers0