Hackathon_Java_tasks/segmentTree.java at DSA · prathamesh424/Hackathon_Java_tasks · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
public class segmentTree {


    public static void main(String[] args) {
        int [] arr  = {3,8,7,6,-2 ,-8 ,4 , 9} ;
        segmentTree st  = new segmentTree(arr) ;

    }

    public static  class  Node {
        int data ;
        int startInterval ;
        int endInterval ;
        Node left ;
        Node right ;

    public Node (int startInterval , int endInterval ){
        this.startInterval= startInterval ;
        this.endInterval = endInterval  ;

    }
    }

    Node root  ;
       // tree meaking
    public  segmentTree(int[] arr) {
        this.root = constructor (arr , 0 , arr.length -1);

    }
                // conditions
    private Node constructor (int [] arr , int start , int end){
        if (start == end ){
            Node leaf  = new Node(start , end);
            leaf.data = arr[start];
            return leaf ;
        }

        Node node = new Node(start, end);
        int mid = (start+ end) / 2 ;

        node.left = this.constructor(arr, start, mid);
        node.right = this.constructor(arr, mid+1, end) ;

        node.data = node.left.data + node.right.data ;

        return node ;

    }


    public void display (){
        display(root);
    }

    private void display (Node node ){
        String st = "";

        if (node.left != null){
            st = st + "Interval = [" + node.left.startInterval + "-" + node.left.endInterval + "] and data is " + node.left.data  + " => " ;
        }
        else  {
             st= st + "there is no left child " ;

        }

         st = st + "Interval = [" + node.left.startInterval + "-" + node.left.endInterval + "] and data is " + node.data  + " <= " ;

        if (node.right != null){
            st = st + "Interval = [" + node.left.startInterval + "-" + node.right.endInterval + "] and data is " + node.right.data  + " => " ;
        }
        else  {
             st= st + "there is no right  child " ;

        }

        System.out.println( st);

        if (node.left != null){
            display(node.left);

        }

        if (node.right != null){
            display(node.right);
        }
    }


    // finding query :=

    public int query (int qStart , int qEnd){
        return query(this.root , qStart, qEnd);
    }

    private int query (Node node  ,int qStart , int qEnd){
        // completely inside
        if (node.startInterval >= qStart && node.endInterval <= qEnd) {
            return node.data ;

        }
        // completely outside
        else if (node.startInterval > qStart || node.endInterval < qEnd){
            return 0 ;

        }
        else{
            return this.query(node.left, qStart, qEnd) + this.query(node.right, qStart, qEnd);

        }

    }

    public void update1 (int index , int value){
        this.root.data = update2( this.root ,index, value);

    }

    private int update2 (Node node ,int index , int value){
        if (index >= node.startInterval && index <= node.endInterval){
            if (index == node.startInterval && index == node.endInterval){
                node.data =value ;
                return node.data ;
            }
            else {
                int leftAns = update2( node.left ,index, value);
                int rightAns = update2( node.right ,index, value);
                node.data = leftAns + rightAns ;
                 return node.data ;

            }
        }

        return node.data ;


    }


}