mrchnk
/ segment-tree.lua
Created
September 20, 2021 10:44
Segment Tree (update by segment, query by index)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function SegmentTree(size, merge, zero) | |
| local tree = {} | |
| local function get(v, tl, tr, index) | |
| local value = tree[v] or zero | |
| if tl == tr then | |
| return value | |
| end | |
| local tm = math.floor((tl + tr) / 2) | |
| if index <= tm then |
mrchnk
/ segment-tree.lua
Last active
January 26, 2022 19:11
Segment Tree (update by index, query by segment)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function SegmentTree(size, merge, zero) | |
| local tree = {} | |
| local function query(v, tl, tr, l, r) | |
| if l == tl and r == tr then | |
| return tree[v] or zero | |
| end | |
| local tm = math.floor((tl + tr) / 2) | |
| if (r <= tm) then | |
| return query(v * 2, tl, tm, l, r) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function BinaryHeap(cmp) | |
| local heap = {} | |
| local function push(el) | |
| table.insert(heap, el) | |
| local i = #heap | |
| while i > 1 do | |
| local parent = math.floor(i / 2) | |
| if cmp(heap[parent], heap[i]) then | |
| break |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function BinarySearchTree(cmp) | |
| local root | |
| local size = 0 | |
| local function has(v, el) | |
| if not v then | |
| return false | |
| end | |
| if v.value == el then | |
| return true | |
| end |
mrchnk
/ BinaryHeap.cs
Last active
July 13, 2021 07:05
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class BinaryHeap<T> | |
| { | |
| public T[] Heap { get; } | |
| public int Count { get; private set; } | |
| public IComparer<T> Comparer { get; } | |
| public BinaryHeap(int size, IComparer<T> comparer = null) | |
| { | |
| Heap = new T[size]; | |
| Count = 0; |
mrchnk
/ SegmentTree.java
Created
May 21, 2021 19:35
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| private static class SegmentTree { | |
| private final long[] tree; | |
| private final int size; | |
| public SegmentTree(int size) { | |
| this.tree = new long[size * 4]; | |
| this.size = size; | |
| } |
mrchnk
/ segment_tree.py
Last active
May 18, 2021 08:09
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class SegmentTree: | |
| def __init__(self, size, merge=min, default=0): | |
| self.size = size | |
| self.merge = merge | |
| self.tree = [default] * size * 4 | |
| pass | |
| def build(self, values): | |
| self._build(0, 0, self.size-1, values) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import time | |
| def timeit(f): | |
| def _f(*args, **nargs): | |
| begin = time.time() | |
| r = f(*args, **nargs) | |
| end = time.time() | |
| print('Time %2.22f ms' % ((end - begin) * 1000)) | |
| return r |
mrchnk
/ adt-undocumented-params.txt
Created
May 11, 2021 16:56
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Common | |
| -Xnovalidate | |
| -XnoAneValidate | |
| -Xruntime RUNTIME_DIR | |
| set | |
| -Xdebug | |
| For IPA-packaging |
mrchnk
/ segment-tree.js
Last active
April 23, 2021 06:34
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function SegmentTree(size, merge, zero) { | |
| const tree = []; | |
| return { | |
| tree, | |
| update(index, value) { | |
| update(0, 0, size - 1, index, value) | |
| }, | |
| query(l, r) { | |
| return query(0, 0, size - 1, l, r) | |
| }, |
NewerOlder