This contract is not finished yet. I am still adding further optimizations and comments. Below is a current snapshot of gas savings using Openzeppelin's MerkleProof Implementation as a baseline.
╭──────────────────────┬─────────────────┬──────┬────────┬──────┬─────────╮
│ MerkleProof contract ┆ ┆ ┆ ┆ ┆ │
╞══════════════════════╪═════════════════╪══════╪════════╪══════╪═════════╡
│ Deployment Cost ┆ Deployment Size ┆ ┆ ┆ ┆ │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ 105953 ┆ 561 ┆ ┆ ┆ ┆ │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ Function Name ┆ min ┆ avg ┆ median ┆ max ┆ # calls │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ verify ┆ 1437 ┆ 1437 ┆ 1437 ┆ 1437 ┆ 1 │
╰──────────────────────┴─────────────────┴──────┴────────┴──────┴─────────╯
╭───────────────────────────────┬─────────────────┬─────┬────────┬─────┬─────────╮
│ OptimizedMerkleProof contract ┆ ┆ ┆ ┆ ┆ │
╞═══════════════════════════════╪═════════════════╪═════╪════════╪═════╪═════════╡
│ Deployment Cost ┆ Deployment Size ┆ ┆ ┆ ┆ │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ 66517 ┆ 364 ┆ ┆ ┆ ┆ │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ Function Name ┆ min ┆ avg ┆ median ┆ max ┆ # calls │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌┼╌╌╌╌╌┼╌╌╌╌╌╌╌╌╌┤
│ verifyProof ┆ 893 ┆ 893 ┆ 893 ┆ 893 ┆ 1 │
╰───────────────────────────────┴─────────────────┴─────┴────────┴─────┴─────────╯
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent