FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
java-tools/other/segment_tree1.java at master · javaarchive/java-tools · GitHub
This repository was archived by the owner on Feb 29, 2024. It is now read-only.
javaarchive
/
java-tools
Public archive
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
java-tools
/
other
/
segment_tree1.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
85 lines (83 loc) · 2.56 KB
Breadcrumbs
java-tools
/
other
/
segment_tree1.java
Copy path
File metadata and controls
85 lines (83 loc) · 2.56 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
import
java
.
util
.*;
public
class
segment_tree1
{
public
static
int
min
(
int
x
,
int
y
) {
//return Math.min(x, y);
return
(
x
<
y
) ?
x
:
y
;
}
public
static
final
int
NO_VALUE
=
0
;
public
static
int
div
(
int
a
,
int
b
) {
return
(
int
)
Math
.
floor
(
a
/
b
);
}
public
static
int
calc_half1
(
int
x
,
int
y
) {
return
div
((
y
-
x
) -
1
,
2
);
}
public
static
int
calc_half2
(
int
x
,
int
y
) {
return
div
((
y
-
x
),
2
) +
1
;
}
public
static
int
getMid
(
int
s
,
int
e
) {
return
s
+ (
e
-
s
) /
2
;
}
public
static
int
getMaxSize
(
int
x
) {
return
2
* (
int
)
Math
.
pow
(
2
,
x
) -
1
;
}
public
static
int
pow2
(
int
x
) {
return
(
int
)
Math
.
pow
(
2
,
x
);
}
public
static
int
[]
st
;
public
static
int
[]
segmenttree
(
int
[]
arr
) {
st
=
new
int
[
getMaxSize
(
arr
.
length
)];
int
n
=
arr
.
length
;
recur_st
(
arr
,
0
,
n
-
1
,
0
);
return
st
;
}
static
int
times_recuron
=
0
;
public
static
int
recur_st
(
int
[]
arr
,
int
a
,
int
b
,
int
c
) {
times_recuron
++;
if
(
times_recuron
>
1000
) {
return
0
;
}
if
(
a
==
b
) {
st
[
c
] =
arr
[
a
];
return
arr
[
a
];
}
int
mid
=
getMid
(
a
,
b
);
st
[
c
] =
recur_st
(
arr
,
a
,
mid
,
c
*
2
+
1
) +
recur_st
(
arr
,
mid
+
1
,
b
,
c
*
2
+
2
);
return
st
[
c
];
}
public
static
int
getsum
(
int
a
,
int
b
,
int
c
,
int
d
,
int
e
){
if
(
c
<=
a
&&
d
>=
b
)
return
st
[
e
];
if
(
b
<
c
||
a
>
d
)
return
0
;
int
mid
=
getMid
(
a
,
b
);
return
getsum
(
a
,
mid
,
c
,
d
,
2
*
e
+
1
) +
getsum
(
mid
+
1
,
b
,
c
,
d
,
2
*
e
+
2
);
}
public
static
int
recursionRMQ
(
int
a
,
int
b
,
int
c
,
int
d
,
int
index
){
if
(
c
<=
a
&&
d
>=
b
)
return
st
[
index
];
// Lookup when done
if
(
b
<
c
||
a
>
d
)
return
Integer
.
MAX_VALUE
;
// This is my infinite value
int
mid
=
getMid
(
a
,
b
);
return
min
(
recursionRMQ
(
a
,
mid
,
c
,
d
,
2
*
index
+
1
),
recursionRMQ
(
mid
+
1
,
b
,
c
,
d
,
2
*
index
+
2
));
}
public
static
int
RMQ
(
int
n
,
int
a
,
int
b
)
{
if
(
b
>
n
-
1
||
a
>
b
||
a
<
0
) {
System
.
out
.
println
(
"input not valid"
);
return
-
1
;
}
return
recursionRMQ
(
0
,
n
-
1
,
a
,
b
,
0
);
}
public
static
void
main
(
String
[]
args
) {
System
.
out
.
println
(
"Self Test segement tree"
);
System
.
out
.
println
(
"From 0 to 6: "
+
calc_half1
(
0
,
6
));
//int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
//int[] arr = {1,2,3,4,5,6};
//int[] arr ={1, 3, 5, 7, 9, 11};
//System.out.println(1 << 2);
int
[]
arr
= {
0
,
5
,
2
,
5
,
4
,
3
,
1
,
6
,
3
};
System
.
out
.
println
(
Arrays
.
toString
(
segmenttree
(
arr
)));
System
.
out
.
println
(
"RMQ: "
+
RMQ
(
arr
.
length
,
2
,
7
));
}
}
Back
|
FazBrowse Home
|
New Git URL