You are not logged in. Please login at www.codechef.com to post your questions!

×

Can anyone Convert this Java code to C++ ?[Segment Tree Implementation]

I am trying to learn segment tree from an youtube video but that guy has coded in JAVA whereas I only understand c++ for now. Can anyone help me ? It can be a great help for other people too who want to learn segment tree as the explanation provided by this guy is awesome. Here's the code.

Thanks in Advance.

package com.interview.tree;

import com.interview.bits.NextPowerOf2;


public class SegmentTreeMinimumRangeQuery {

/**
 * Creates a new segment tree based off input array.
 */
public int[] createSegmentTree(int input[]){
    NextPowerOf2 np2 = new NextPowerOf2();
    //if input len is pow of then size of 
    //segment tree is 2*len -1 otherwisze
    //size of segment tree is next (pow of 2 for len) * 2 -1
    int nextPowOfTwo = np2.nextPowerOf2(input.length);
    int segmentTree[] = new int[nextPowOfTwo*2 -1];

    for(int i=0; i < segmentTree.length; i++){
        segmentTree[i] = Integer.MAX_VALUE;
    }
    constructMinSegmentTree(segmentTree, input, 0, input.length - 1, 0);
    return segmentTree;

}

/**
 * Updates segment tree for certain index by given delta
 */
public void updateSegmentTree(int input[], int segmentTree[], int index, int delta){
    input[index] += delta;
    updateSegmentTree(segmentTree, index, delta, 0, input.length - 1, 0);
}

/**
 * Updates segment tree for given range by given delta
 */
public void updateSegmentTreeRange(int input[], int segmentTree[], int startRange, int endRange, int delta) {
    for(int i = startRange; i <= endRange; i++) {
        input[i] += delta;
    }
    updateSegmentTreeRange(segmentTree, startRange, endRange, delta, 0, input.length - 1, 0);
}

/**
 * Queries given range for minimum value.
 */
public int rangeMinimumQuery(int []segmentTree,int qlow,int qhigh,int len){
    return rangeMinimumQuery(segmentTree,0,len-1,qlow,qhigh,0);
}

/**
 * Updates given range by given delta lazily
 */
public void updateSegmentTreeRangeLazy(int input[], int segmentTree[], int lazy[], int startRange, int endRange, int delta) {
    updateSegmentTreeRangeLazy(segmentTree, lazy, startRange, endRange, delta, 0, input.length - 1, 0);
}

/**
 * Queries given range lazily
 */
public int rangeMinimumQueryLazy(int segmentTree[], int lazy[], int qlow, int qhigh, int len) {
    return rangeMinimumQueryLazy(segmentTree, lazy, qlow, qhigh, 0, len - 1, 0);
}

private void constructMinSegmentTree(int segmentTree[], int input[], int low, int high,int pos){
    if(low == high){
        segmentTree[pos] = input[low];
        return;
    }
    int mid = (low + high)/2;
    constructMinSegmentTree(segmentTree, input, low, mid, 2 * pos + 1);
    constructMinSegmentTree(segmentTree, input, mid + 1, high, 2 * pos + 2);
    segmentTree[pos] = Math.min(segmentTree[2*pos+1], segmentTree[2*pos+2]);
}

private void updateSegmentTree(int segmentTree[], int index, int delta, int low, int high, int pos){

    //if index to be updated is less than low or higher than high just return.
    if(index < low || index > high){
        return;
    }

    //if low and high become equal, then index will be also equal to them and update
    //that value in segment tree at pos
    if(low == high){
        segmentTree[pos] += delta;
        return;
    }
    //otherwise keep going left and right to find index to be updated 
    //and then update current tree position if min of left or right has
    //changed.
    int mid = (low + high)/2;
    updateSegmentTree(segmentTree, index, delta, low, mid, 2 * pos + 1);
    updateSegmentTree(segmentTree, index, delta, mid + 1, high, 2 * pos + 2);
    segmentTree[pos] = Math.min(segmentTree[2*pos+1], segmentTree[2*pos + 2]);
}

private void updateSegmentTreeRange(int segmentTree[], int startRange, int endRange, int delta, int low, int high, int pos) {
    if(low > high || startRange > high || endRange < low ) {
        return;
    }

    if(low == high) {
        segmentTree[pos] += delta;
        return;
    }

    int middle = (low + high)/2;
    updateSegmentTreeRange(segmentTree, startRange, endRange, delta, low, middle, 2 * pos + 1);
    updateSegmentTreeRange(segmentTree, startRange, endRange, delta, middle + 1, high, 2 * pos + 2);
    segmentTree[pos] = Math.min(segmentTree[2*pos+1], segmentTree[2*pos+2]);
}

private int rangeMinimumQuery(int segmentTree[],int low,int high,int qlow,int qhigh,int pos){
    if(qlow <= low && qhigh >= high){
        return segmentTree[pos];
    }
    if(qlow > high || qhigh < low){
        return Integer.MAX_VALUE;
    }
    int mid = (low+high)/2;
    return Math.min(rangeMinimumQuery(segmentTree, low, mid, qlow, qhigh, 2 * pos + 1),
            rangeMinimumQuery(segmentTree, mid + 1, high, qlow, qhigh, 2 * pos + 2));
}

private void updateSegmentTreeRangeLazy(int segmentTree[],
                                        int lazy[], int startRange, int endRange,
                                        int delta, int low, int high, int pos) {
    if(low > high) {
        return;
    }

    //make sure all propagation is done at pos. If not update tree
    //at pos and mark its children for lazy propagation.
    if (lazy[pos] != 0) {
        segmentTree[pos] += lazy[pos];
        if (low != high) { //not a leaf node
            lazy[2 * pos + 1] += lazy[pos];
            lazy[2 * pos + 2] += lazy[pos];
        }
        lazy[pos] = 0;
    }

    //no overlap condition
    if(startRange > high || endRange < low) {
        return;
    }

    //total overlap condition
    if(startRange <= low && endRange >= high) {
        segmentTree[pos] += delta;
        if(low != high) {
            lazy[2*pos + 1] += delta;
            lazy[2*pos + 2] += delta;
        }
        return;
    }

    //otherwise partial overlap so look both left and right.
    int mid = (low + high)/2;
    updateSegmentTreeRangeLazy(segmentTree, lazy, startRange, endRange,
            delta, low, mid, 2*pos+1);
    updateSegmentTreeRangeLazy(segmentTree, lazy, startRange, endRange,
            delta, mid+1, high, 2*pos+2);
    segmentTree[pos] = Math.min(segmentTree[2*pos + 1], segmentTree[2*pos + 2]);
}

private int rangeMinimumQueryLazy(int segmentTree[], int lazy[], int qlow, int qhigh,
                                  int low, int high, int pos) {

    if(low > high) {
        return Integer.MAX_VALUE;
    }

    //make sure all propagation is done at pos. If not update tree
    //at pos and mark its children for lazy propagation.
    if (lazy[pos] != 0) {
        segmentTree[pos] += lazy[pos];
        if (low != high) { //not a leaf node
            lazy[2 * pos + 1] += lazy[pos];
            lazy[2 * pos + 2] += lazy[pos];
        }
        lazy[pos] = 0;
    }

    //no overlap
    if(qlow > high || qhigh < low){
        return Integer.MAX_VALUE;
    }

    //total overlap
    if(qlow <= low && qhigh >= high){
        return segmentTree[pos];
    }

    //partial overlap
    int mid = (low+high)/2;
    return Math.min(rangeMinimumQueryLazy(segmentTree, lazy, qlow, qhigh,
                    low, mid, 2 * pos + 1),
            rangeMinimumQueryLazy(segmentTree, lazy,  qlow, qhigh,
                    mid + 1, high, 2 * pos + 2));

}

public static void main(String args[]){
    SegmentTreeMinimumRangeQuery st = new SegmentTreeMinimumRangeQuery();

    int input[] = {0,3,4,2,1,6,-1};
    int segTree[] = st.createSegmentTree(input);

    //non lazy propagation example
    assert 0 == st.rangeMinimumQuery(segTree, 0, 3, input.length);
    assert 1 == st.rangeMinimumQuery(segTree, 1, 5, input.length);
    assert -1 == st.rangeMinimumQuery(segTree, 1, 6, input.length);
    st.updateSegmentTree(input, segTree, 2, 1);
    assert 2 == st.rangeMinimumQuery(segTree, 1, 3, input.length);
    st.updateSegmentTreeRange(input, segTree, 3, 5, -2);
    assert -1 == st.rangeMinimumQuery(segTree, 5, 6, input.length);
    assert 0 == st.rangeMinimumQuery(segTree, 0, 3, input.length);

    //lazy propagation example
    int input1[] = {-1,2,4,1,7,1,3,2};
    int segTree1[] = st.createSegmentTree(input1);
    int lazy1[] =  new int[segTree.length];
    st.updateSegmentTreeRangeLazy(input1, segTree1, lazy1, 0, 3, 1);
    st.updateSegmentTreeRangeLazy(input1, segTree1, lazy1, 0, 0, 2);
    assert 1 == st.rangeMinimumQueryLazy(segTree1, lazy1, 3, 5, input1.length);
}

}

asked 28 Aug '15, 02:05

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

edited 28 Aug '15, 02:06


Hi shubham,

for converting this code to c++ you just need to copy paste the function and remove "private" keyword.

copy all lines of code of main function and paste in side c++ main function and do not create object of class to call a function because you can call functions without using object in c++.

and for array creation - create array as you do in c++ because in java array initialization is different and for getting next power of 2 you should use simple method like 2*number to get child node.

just go for those segment tree code which do not include library function that would be better for competitive programming purpose you can find several code on blogs etc.

if you have any problem then ask.

link

answered 28 Aug '15, 14:17

admin123's gravatar image

5★admin123
1.2k12
accept rate: 28%

try j2c to convert java source to c++ .

link

answered 07 Sep '15, 22:34

sunnyvilles's gravatar image

0★sunnyvilles
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×1,912
×1,477
×1,302
×4

question asked: 28 Aug '15, 02:05

question was seen: 1,267 times

last updated: 07 Sep '15, 22:34