# SegmentTree.sol

Pure Solidity library，用固定大小的线段树表示 99 个价格 tick（1--99）。`OrderBook` 在内部使用它跟踪每个 tick 的 bid/ask volume，并为 Frequent Batch Auctions 计算最优清算价格。

## Layout

该树由一个 `uint256[256]` array（`Tree.nodes`）表示，采用 1-indexed 布局：

```
               nodes[1] = root (total volume)
              /                              \
        nodes[2]                          nodes[3]
       /        \                        /        \
    nodes[4]  nodes[5]  ...          ...       nodes[7]
     ...                                          ...
  nodes[128] nodes[129] ... nodes[226]  nodes[227] ... nodes[255]
    tick 1     tick 2        tick 99     (unused padding)
```

* **Leaves:** indices 128--226（tick `i` 映射至 leaf index `127 + i`）。
* **Internal nodes:** indices 1--127。
* **Root:** `nodes[1]` 存储所有 tick 的总 volume。
* **Unused:** leaf indices 227--255 为 padding（大于等于 99 的下一个 2 的幂是 128）。

每个节点都存储其 subtree 的总 volume。

## Constants

| Constant   | Value | Description                           |
| ---------- | ----- | ------------------------------------- |
| `LEAVES`   | 128   | Next power-of-2 >= 99                 |
| `SIZE`     | 256   | Array length (2 \* LEAVES, 1-indexed) |
| `MAX_TICK` | 99    | 最大有效 tick                             |

## 存储 Struct

```solidity
struct Tree {
    uint256[256] nodes;
}
```

## 函数

所有操作都是 **O(log 128) = O(7)** 次 storage reads/writes。

### update

```solidity
function update(Tree storage tree, uint256 tick, int256 delta) internal
```

为指定 tick 添加或移除 volume。`delta` 为 signed: 正数表示增加 volume，负数表示移除 volume。函数会从 leaf 向上走向 root，并更新每个 ancestor node。

* 如果 `tick` 不在 \[1, 99] 内，则 revert。
* 如果发生 underflow（移除的 volume 超过某个节点现有 volume），则 revert。

### prefixSum

```solidity
function prefixSum(Tree storage tree, uint256 tick) internal view returns (uint256 sum)
```

返回 ticks \[1, tick]（含两端）的累计 volume。该函数在线段树上执行标准 recursive range query。

* 如果 `tick` 不在 \[1, 99] 内，则 revert。

### findClearingTick

```solidity
function findClearingTick(
    Tree storage bidTree,
    Tree storage askTree
) internal view returns (uint256 clearingTick)
```

对于 Frequent Batch Auction，通过 binary search 查找最优清算 tick。算法如下：

1. **tick p 处的累计 bid:** ticks >= p 的总 bid volume（bid 愿意支付至少 p）。计算方式为 `totalBidVolume - prefixSum(bidTree, p-1)`。
2. **tick p 处的累计 ask:** ticks <= p 的总 ask volume（ask 愿意以至多 p 卖出）。计算方式为 `prefixSum(askTree, p)`。
3. **Clearing tick:** \[1, 99] 中满足 `cumBid(p) >= cumAsk(p)` 的最高 `p`。
4. **Tie-break 校正:** 找出 candidate 后，检查 `p+1`，并选择能够最大化 matched volume（`min(cumBid, cumAsk)`）的 tick。

如果没有 crossing（没有有效清算 tick），则返回 0。

### totalVolume

```solidity
function totalVolume(Tree storage tree) internal view returns (uint256)
```

返回 root node 的值，即所有 tick 中存储的总 volume。这是一次 O(1) read。

### volumeAt

```solidity
function volumeAt(Tree storage tree, uint256 tick) internal view returns (uint256)
```

返回指定 tick 的 volume（leaf value）。这是一次 O(1) read。

* 如果 `tick` 不在 \[1, 99] 内，则 revert。

## 在订单簿中的用法

`OrderBook` 为每个市场维护两棵线段树：

* `bidTrees[marketId]` -- 跟踪每个 tick 的 bid volume。
* `askTrees[marketId]` -- 跟踪每个 tick 的 ask volume。

当订单以 tick `t` 和 `n` lots 提交时，系统调用 `update(tree, t, int256(n))`。取消订单时，调用 `update(tree, t, -int256(n))`。清算时调用 `findClearingTick(bidTrees[id], askTrees[id])`。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.strike.pm/zh/zhi-neng-he-yue/segment-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.