Struktury danych

{
  "name": "John Doe",
  "age": 30,
  "isEmployed": true,
  "roles": ["developer", "admin"],
  "address": {
    "city": "New York",
    "zip": "10001"
  }
}

const ids = new Set<number>();
ids.add(42);
console.log(ids.has(42)); // true

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
System.out.println(pq.poll()); // 1

let capacity = 4;
let size = 0;

function append(x: number) {
  if (size === capacity) {
    capacity *= 2; // resize + copy O(n)
  }
  size++;
}

class DSU {
  private parent: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }

  find(x: number): number {
    if (this.parent[x] === x) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(a: number, b: number) {
    const ra = this.find(a);
    const rb = this.find(b);
    if (ra !== rb) this.parent[rb] = ra;
  }
}

type Node = { key: string; prev?: Node; next?: Node }

// idea:
// map: key -> node
// list: head <-> ... <-> tail
// get(key): move node to head (O(1))
// put(key): insert/move to head; if over capacity, evict tail (O(1))

class Fenwick {
  private bit: number[];

  constructor(n: number) {
    this.bit = Array(n + 1).fill(0);
  }

  add(i: number, delta: number) {
    for (let x = i + 1; x < this.bit.length; x += x & -x) this.bit[x] += delta;
  }

  sum(i: number) {
    let res = 0;
    for (let x = i + 1; x > 0; x -= x & -x) res += this.bit[x];
    return res;
  }
}

class SegTree {
  private tree: number[];
  private n: number;

  constructor(n: number) {
    this.n = n;
    this.tree = Array(4 * n).fill(0);
  }

  update(node: number, l: number, r: number, idx: number, val: number) {
    if (l === r) {
      this.tree[node] = val;
      return;
    }
    const mid = Math.floor((l + r) / 2);
    if (idx <= mid) this.update(node * 2, l, mid, idx, val);
    else this.update(node * 2 + 1, mid + 1, r, idx, val);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];
  }
}