Skip to content

Commit e12b599

Browse files
kunal-kushwahakunal-kushwaha
committed
segment trees
1 parent 20cb65a commit e12b599

5 files changed

Lines changed: 181 additions & 0 deletions

File tree

‎lectures/20-trees/code/Segment trees/Main.java‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
class Main {
2+
public static void main(String[] args) {
3+
int[] arr = {3, 8, 6, 7, -2, -8, 4, 9};
4+
SegmentTree tree = new SegmentTree(arr);
5+
// tree.display();
6+
7+
System.out.println(tree.query(1, 6));
8+
}
9+
}

‎lectures/20-trees/code/Segment trees/SegmentTree.java‎

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
class SegmentTree {
2+
3+
private static class Node {
4+
int data;
5+
int startInterval;
6+
int endInterval;
7+
Node left;
8+
Node right;
9+
10+
public Node (int startInterval, int endInterval) {
11+
this.startInterval = startInterval;
12+
this.endInterval = endInterval;
13+
}
14+
}
15+
16+
Node root;
17+
18+
public SegmentTree(int[] arr) {
19+
// create a tree using this array
20+
this.root = constructTree(arr, 0, arr.length - 1);
21+
}
22+
23+
private Node constructTree(int[] arr, int start, int end) {
24+
if(start == end) {
25+
// leaf node
26+
Node leaf = new Node(start, end);
27+
leaf.data = arr[start];
28+
return leaf;
29+
}
30+
31+
// create new node with index you are at
32+
Node node = new Node(start, end);
33+
34+
int mid = (start + end) / 2;
35+
36+
node.left = this.constructTree(arr, start, mid);
37+
node.right = this.constructTree(arr, mid + 1, end);
38+
39+
node.data = node.left.data + node.right.data;
40+
return node;
41+
}
42+
43+
public void display() {
44+
display(this.root);
45+
}
46+
private void display(Node node) {
47+
String str = "";
48+
49+
if(node.left != null) {
50+
str = str + "Interval=[" + node.left.startInterval + "-" + node.left.endInterval + "] and data: " + node.left.data + " => ";
51+
} else {
52+
str = str + "No left child";
53+
}
54+
55+
// for current node
56+
str = str + "Interval=[" + node.startInterval + "-" + node.endInterval + "] and data: " + node.data + " <= ";
57+
58+
if(node.right != null) {
59+
str = str + "Interval=[" + node.right.startInterval + "-" + node.right.endInterval + "] and data: " + node.right.data;
60+
} else {
61+
str = str + "No right child";
62+
}
63+
64+
System.out.println(str + '\n');
65+
66+
// call recursion
67+
if(node.left != null) {
68+
display(node.left);
69+
}
70+
71+
if(node.right != null) {
72+
display(node.right);
73+
}
74+
}
75+
76+
// query
77+
public int query(int qsi, int qei) {
78+
return this.query(this.root, qsi, qei);
79+
}
80+
private int query(Node node, int qsi, int qei) {
81+
if(node.startInterval >= qsi && node.endInterval <= qei) {
82+
// node is completely lying inside query
83+
return node.data;
84+
} else if (node.startInterval > qei || node.endInterval < qsi) {
85+
// completely outside
86+
return 0;
87+
} else {
88+
return this.query(node.left, qsi, qei) + this.query(node.right, qsi, qei);
89+
}
90+
}
91+
92+
// update
93+
public void update(int index, int value) {
94+
this.root.data = update(this.root, index, value);
95+
}
96+
private int update(Node node, int index, int value) {
97+
if (index >= node.startInterval&& index <= node.endInterval){
98+
if(index == node.startInterval && index == node.endInterval) {
99+
node.data = value;
100+
return node.data;
101+
} else {
102+
int leftAns = update(node.left, index, value);
103+
int rightAns = update(node.right, index, value);
104+
node.data = leftAns + rightAns;
105+
return node.data;
106+
}
107+
}
108+
return node.data;
109+
}
110+
111+
}

‎lectures/20-trees/code/Segment trees/pom.xml‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
<project>
2+
<modelVersion>4.0.0</modelVersion>
3+
<groupId>mygroupid</groupId>
4+
<artifactId>myartifactid</artifactId>
5+
<version>0.0-SNAPSHOT</version>
6+
<dependencies>
7+
<dependency>
8+
<groupId>junit</groupId>
9+
<artifactId>junit</artifactId>
10+
<version>4.12</version>
11+
<type>jar</type>
12+
</dependency>
13+
<dependency>
14+
<groupId>com.googlecode.json-simple</groupId>
15+
<artifactId>json-simple</artifactId>
16+
<version>1.1.1</version>
17+
<type>jar</type>
18+
</dependency>
19+
<dependency>
20+
<groupId>org.hamcrest</groupId>
21+
<artifactId>hamcrest-core</artifactId>
22+
<version>1.3</version>
23+
<type>jar</type>
24+
</dependency>
25+
</dependencies>
26+
<build>
27+
<plugins>
28+
<plugin>
29+
<groupId>de.qaware.maven</groupId>
30+
<artifactId>go-offline-maven-plugin</artifactId>
31+
<version>1.2.5</version>
32+
<configuration>
33+
<dynamicDependencies>
34+
<DynamicDependency>
35+
<groupId>org.apache.maven.surefire</groupId>
36+
<artifactId>surefire-junit4</artifactId>
37+
<version>2.20.1</version>
38+
<classifier></classifier>
39+
<repositoryType>PLUGIN</repositoryType>
40+
</DynamicDependency>
41+
<DynamicDependency>
42+
<groupId>com.querydsl</groupId>
43+
<artifactId>querydsl-apt</artifactId>
44+
<version>4.2.1</version>
45+
<classifier>jpa</classifier>
46+
<repositoryType>MAIN</repositoryType>
47+
</DynamicDependency>
48+
</dynamicDependencies>
49+
</configuration>
50+
</plugin>
51+
</plugins>
52+
</build>
53+
</project>

‎lectures/20-trees/code/Segment trees/replit.nix‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
{ pkgs }: {
2+
deps = [
3+
pkgs.graalvm17-ce
4+
pkgs.maven
5+
pkgs.replitPackages.jdt-language-server
6+
pkgs.replitPackages.java-debug
7+
];
8+
}

‎lectures/20-trees/notes/Trees - 3 (Segment).pdf‎

1.33 MB
Binary file not shown.

0 commit comments

Comments
 (0)