← Back to the Archives

The rituals of the n-th survivor

· 10 min read ·algorithms
javascripttypescriptperformancefenwick-treelinked-list

The problem: I have a vast array of items - numbers, in fact. What is needed of me is to ritualistically perform n-th remaining element severance. Repeatedly. Using such methods like splice came to me initially, but the scale of the problem... I need something better.

Known unknowns

As soon as Array.prototype.splice called for implementation, I thought it'd be enough. I was so wrong.

The trap is not being right or wrong. Every following approach gives me the same result, the same survivors. The trap is more sinister, it is shifting. Each removal moves every element on the right one slot left. Every. Single. One... Perform this thousands of times, because the host is enormous, and you'll be changing things you never needed to.

Undeniable truths

Given an input array, process each element in order:

Sigil Rite
n < 0 Bind the value into result
n > 0 Sever the n-th remaining survivor from result (1-indexed), if still in bounds
n = 0 Pass in silence

Each ritual rewrites what "2nd" or "3rd" means for the next iteration. That shifting is the source of the problem.

flowchart TD IN["Input: [-3, 5, -1, 2, -4]"] IN --> P1["Phase 1: gather negatives<br/>[-3, -1, -4] · positions 1, 2, 3"] P1 --> P2["Phase 2: apply positives in order"] P2 --> S5{"Sigil 5<br/>only 3 survivors"} S5 -->|"skip"| S2["Sigil 2: sever 2nd survivor"] S2 --> OUT["Result: [-3, -4]"]

Where rites on array go awry...

Naive splice on a dense array. Every severance copies the tail.

flowchart TD subgraph before["Before: sever index 1"] direction LR b0["0<br/>-3"] --> b1["1<br/>-1"] --> b2["2<br/>-4"] --> b3["3<br/>-7"] --> b4["4<br/>-2"] end before -->|"every element after index 1<br/>dragged left - O(N) copy"| after subgraph after["After"] direction LR a0["0<br/>-3"] --> a1["1<br/>-4"] --> a2["2<br/>-7"] --> a3["3<br/>-2"] end

What the complexity oracle whispered - no fixture required, only the shape of the work:

Approach Per severance Accumulated toll (rough)
splice on array O(N) tail copy O(removals × N) - punishing when both stay large
Linked chain O(k) walk + O(1) cut O(removals × avg k) - gentle when k stays small
Fenwick tally tree O(log N) find + O(log N) update O(removals × log N) - steady even when k grows

Same survivors, different price. The naive rite is correct until the host grows vast enough to notice.

Poltergeist in the machine

Item Detail
Operation Sever the k-th remaining survivor from a live collection
Naive rite result.splice(k - 1, 1) on a JavaScript array
Per-severance cost O(N) - every trailing element shifts left
At scale Removals × average host length → quadratic or worse in practice
What we actually need Locate the k-th survivor and banish it without moving the rest

Two ritual structures answer that summons. Same goal, different temperament.

Ritual of Completion - the Chain of Survivors

Idea: Store the bound values as nodes in a doubly-linked chain. Each node remembers its neighbors. Severing a node is repointing two pointers - no array shifting, no tail dragged through the void.

flowchart LR subgraph initial["Initial host"] head1(["head"]) --> A1["-3<br/>pos 1"] A1 -->|next| B1["-1<br/>pos 2"] B1 -->|prev| A1 B1 -->|next| C1["-4<br/>pos 3"] C1 -->|prev| B1 C1 --> tail1(["tail"]) end subgraph after["After n=2: -1 unlinked"] head2(["head"]) --> A2["-3<br/>pos 1"] A2 -->|next| C2["-4<br/>pos 2"] C2 -->|prev| A2 C2 --> tail2(["tail"]) end

Unlinking (O(1) - two pointers rewired):

flowchart LR subgraph before["Before: sever B"] xA["A"] -->|next| xB["B"] xB -->|prev| xA xB -->|next| xC["C"] xC -->|prev| xB end subgraph after["After: A.next=C, C.prev=A"] yA["A"] -->|next| yC["C"] yC -->|prev| yA end
Step Action Cost
Find k-th Walk k links from head O(k)
Sever Rewire prev/next O(1)

Good when: k stays small on average. Easier to inscribe and to read.

Ritual of Reconstruction - the Tally Tree

Idea: Keep values in fixed slots that never move. A Binary Indexed Tree (Fenwick tree) tracks how many survivors live in each prefix. Data stays put - only alive flags and counts change.

Original slots:  [0]  [1]  [2]  [3]  [4]   ← fixed indices, eternal
Values:          -3   -1   -4   -7   -2
Alive?           ✓    ✓    ✓    ✗    ✓

Prefix counts (survivors up to index i):
  index:     0  1  2  3  4
  alive:     1  2  3  3  4

Find 2nd alive: binary search on the tree - "where does the prefix count first reach 2?"

Want k=2 (2nd survivor):

  "First half holds ≥2 alive?" → yes, descend left
  "First quarter holds ≥2?"    → no, descend right
  ...

  Answer: slot [1] holds -1    ← O(log N) steps through the tally

Banish slot [1]: subtract 1 from every tree cell that covers index 1. The next findKth query reads the updated counts automatically.

Tree structure (conceptual): each index i contributes its count to tree cells at i, i+2, i+4, ... (the i & -i pattern):

graph BT n1["cell 1<br/>index 1"] -->|"i += lowbit"| n2["cell 2<br/>indices 1-2"] n3["cell 3<br/>index 3"] --> n4["cell 4<br/>indices 1-4"] n2 --> n4 n5["cell 5<br/>index 5"] --> n6["cell 6<br/>indices 5-6"] n7["cell 7<br/>index 7"] --> n8["cell 8<br/>indices 1-8"] n4 --> n8 n6 --> n8
Operation What it does Cost
findKth(k) Binary lift on prefix sums O(log N)
add(i, -1) Decrement counts for index i O(log N)
Build final array One pass, skip the banished O(N)

Good when: k can land anywhere and you need predictable speed as N grows.

The way the rituals work within the unknown

Both paths refuse the splice trap. Neither drags trailing elements on severance.

Chain of Survivors Tally Tree
Mental model Beads on a cord - follow links to the k-th, then snip Fixed slots + a counter tree - leap to the k-th alive index
Data movement None (repoint pointers) None (flip flags, update counts)
Find k-th alive Walk k links from head Binary search on prefix sums
Sever Rewire prev/next Mark banished + decrement tree
Cost per severance O(k) O(log N)
Inscription complexity Lower Higher (tree class)
Best for Small average k Large k, predictable performance at scale

Side by side:

CHAIN                               TALLY TREE
─────                               ──────────

[-3]→[-1]→[-4]                      slots:  0  1  2
  │                                  alive: ✓  ✓  ✓
  walk 2 links                       counts in tree
  ↓                                  ↓
[-3]→[-4]                            findKth(2) → index 1
                                     mark banished, update counts

Motion: follow pointers             Motion: jump using tree sums
Cost per severance: O(k)            Cost per severance: O(log N)
Simpler inscription                 Steadier at scale

CHAIN:        repoint 2 pointers          → no copy
TALLY TREE:   flip a flag + update counts → no copy

Worked traces

Example 1 - a small host

Input: [-10, 2, -20, 1, -30]

Phase 1 - gather the bound:

Result: [-10, -20, -30]
    pos    1    2    3

Severance sigils to apply (in order): 2, 1

Chain trace

Initial cord (fixed slots, pointer links):

flowchart LR head(["head"]) --> n0["slot 0<br/>-10<br/>pos 1"] n0 -->|next| n1["slot 1<br/>-20<br/>pos 2"] n1 -->|prev| n0 n1 -->|next| n2["slot 2<br/>-30<br/>pos 3"] n2 -->|prev| n1
Step Sigil Action Chain after
1 2 Walk 2 links: 0→1, unlink slot 1 (-20) [0:-10] → [2:-30]
2 1 Walk 1 link: slot 0, unlink (-10) [2:-30]

Final survivors: [-30]

Tally tree trace

Fixed slots with alive flags (data never moves):

slot:   0      1       2
value: -10    -20     -30
alive:  ✓      ✓      ✓     aliveCount = 3
Step Sigil Action Alive after
1 2 findKth(2) → slot 1 (-20), mark banished slots 0, 2 alive → [-10, -30]
2 1 findKth(1) → slot 0 (-10), mark banished slot 2 alive → [-30]

Final survivors: [-30]

Example 2 - severance sigils out of reach

Input: [-3, 5, -1, 2, -4, 1, -7]

Phase 1 - gather the bound:

Result: [-3, -1, -4, -7]
    pos   1   2   3   4

Severance sigils to apply (in order): 5, 2, 1

Chain trace

Initial cord:

flowchart LR head(["head"]) --> n0["slot 0<br/>-3<br/>pos 1"] n0 -->|next| n1["slot 1<br/>-1<br/>pos 2"] n1 -->|prev| n0 n1 -->|next| n2["slot 2<br/>-4<br/>pos 3"] n2 -->|prev| n1 n2 -->|next| n3["slot 3<br/>-7<br/>pos 4"] n3 -->|prev| n2
Step Sigil Action Chain after
1 5 Skip - position ≥ length (4) unchanged
2 2 Walk 2 links: 0→1, unlink slot 1 (-1) [0:-3] → [2:-4] → [3:-7]
3 1 Walk 1 link: slot 0, unlink (-3) [2:-4] → [3:-7]

Final survivors: [-4, -7]

Tally tree trace

slot:   0     1     2     3
value: -3    -1    -4    -7
alive: ✓     ✓     ✓     ✓     aliveCount = 4
Step Sigil Action Alive after
1 5 Skip - position ≥ alive count (4) unchanged
2 2 findKth(2) → slot 1 (-1), mark banished slots 0, 2, 3 → [-3, -4, -7]
3 1 findKth(1) → slot 0 (-3), mark banished slots 2, 3 → [-4, -7]

Final survivors: [-4, -7]

Why would this way work?

Approach Find k-th survivor Sever When it wins
splice on array O(1) index access O(N) tail copy Never at this scale
Chain of survivors O(k) walk from head O(1) pointer rewire Small average k; simpler inscription
Tally tree O(log N) prefix search O(log N) count update Large k; predictable bounds as N grows

The chain is the readable default - the first rite I inscribe when k tends to stay modest. The tally tree is the one I reach for when severance sigils can land anywhere in a host that refuses to shrink - same survivors, but the cost stays logarithmic instead of linear in N.

Beware of the unseen

Grimoires and scrolls used in esoteric research