如果方法不得当，在诸如游戏之类的抽签中计算动态投注额会消耗很高的算力。下面，让我们看一个比较合适的方案......# D4 p/ b! d) _  w/ A; O4 ~

% c+ Y6 s' p4 H7 b9 i: `    在去中心化的应用程序中，最普遍的抽签方式就是：使用与用户所持有的令牌数量成比例的一个随机数。如果只允许增加用户持有量，这就非常简单。但是，如果你想在所有抽签轮次中自由更改用户持有量时，抽签的随机计算就会变得非常复杂......; h4 J% [3 Z8 |2 |; W* S( Y& R

+ n; x* y6 I( t6 k' l    基本的方式9 i/ U  u9 U, Y# j  L9 M* R
' c/ ?6 d2 M' X$ i( }, L
    构建这样的系统最简单方法是创建一个虚拟列表，其中包含每个参与抽签地址的区段。使用一个存储变量来跟踪列表大小，并且每当有人改变持有量时：
% h$ K* R, u* {
: ^+ ~+ E0 S: @    tokenHolder.segmentStart=segmentSize;
# j: O0 L- {% I$ V! F  [. o( m1 b5 D  c0 n$ M
    segmentSize+=_stake;
$ X! H9 A2 E6 ?4 \7 J1 Z! l3 k. h0 v. z2 Z8 ], a
    tokenHolder.segmentEnd=segmentSize;
0 e9 K2 ~- `2 `) C% t4 V
2 `. s1 @# ]! K3 F    这种方法存在两大问题（尽管根据使用情况，可能不会很严重）。
. |$ p8 G, d( g- f+ m* j# l5 c/ r( m* _$ L9 }! Y& ]+ s
    首先，如果持有人希望更改或删除他们的投入额，那么拼接这个列表的计算成本会很高。/ A  H, ]; O5 p+ Z" \
- v% d# X( L9 i8 R# a
    其次，获得被抽中者需要迭代每位持有者，如下所示：
: B5 D. O' t) W3 _" a$ _
4 B: e# `% P' P! b, F" b    //O(n)wherenisthenumberoftokenholderswithstake3 A; |: `  L: }( O7 v. f

( e/ |' Z  o$ g" U) X  ?2 Y/ l    for(uinti=0;i
. K  q0 A! x8 g7 _2 `( C: |3 y% U1 E2 O5 L
    if(currentDrawnNumber.segmentEnd)
7 v2 d5 Y  Z& z6 |5 o' K1 V$ |
7 B" Q+ O; B6 e  \    returntokenHolders.address# y9 x7 T  ?: X
# C8 t3 p- w8 L9 ?8 K' T( J
    在任何规模可观的系统中，每次抽奖都会需要很多算力。这种算法还制造了O（d*a）个影子漏洞，其中d是抽签次数，a是令牌持有者的数量，因为攻击者可以用最低额创建大量账户。这意味着唯一合理的方法是让令牌持有者检查自己是否被抽出。这严重限制了智能合约实施自动化的逻辑，无法实现自动抽取和通知被抽取者。
! v! |6 _3 E- {  A$ n/ n$ p& V! P' D9 `5 ^- C
    树状数组解决方案6 {8 I6 [* p2 H- q

4 v' ?* A+ O. b- n; m- F" k    在寻求更好的方法过程中，我们的首席技术官ClémentLesaege从一种复杂的数据结构形式里找到了答案：K-Ary树状数组。K-Ary树状数组的每个非数据点都有K个子节点并且保存所有节点的值的总和。这意味着我们关心的实际值都是数据点，经证明以这种方式组织数据对性能有非常大的提高。比如一个二进制的树状数组（K=2），其中Alice有10个令牌投注，Bob有15个令牌投注，Carl有20个令牌投注，Dave有5个令牌投注，看起来像：
* S8 Z" A1 M/ j& A8 _* w& G2 Y
    二进制树状数组示例! p5 v6 q2 @, s; b: `& f% r& B* G
" [( x0 B1 ~8 b3 w  Z
    在以上示例中，假设我们抽取到数字13，寻取方式如下：首先13落在[0-24,25-49]的哪个区？0-24，所以往下进入左侧区域。之后判断13落入[0-9,10-24]的哪个区域？由此抽取到鲍勃。
. w8 `- C. i' G' E' X) [  t! ]6 C4 P0 s( ~/ C
    现在，假设我们抽取到2。同理，从根开始，但是这次27落到25-49，所以我们进入右侧区域。同样对[0-20,21-24]重复相同的过程，但是使用2而不是27，因为您通过跳过第一级中的左节点“花费”了25，于是抽取到了卡尔。
5 Z- O8 x: R* w9 \9 ]" I2 @+ Q9 i5 i/ @% P2 I4 E
    所以这个数据结构让我们的抽取复杂度变为O（K*log（n）/log（K）），其中K是每个节点的子节点数。log（n）/log（K）是遍历K次数据节点数的数值，换句话说，就是数据结构的层级数。将它乘以K是因为在最坏的情况下，你必须查看你遍历的每个节点的每个子节点，以确定是否遍历下一个节点。$ A4 B% s7 A# Z  W5 k4 L6 @0 D
7 c% l8 w: G9 O7 ?5 q1 E
    设置，删除和追加的复杂度都是O（log（n）/log（K）），因为是从给定的数据节点开始，逐级向上操作。注意保留一定量的空闲数据节点，是保证在删除操作中保持数据结构完整的捷径。这些操作非常容易实现：7 K! ^# e. ^( x/ _* ~
( p* ~: [9 N# R) k' I
    设置：设置新值并更新根值。# T$ u) M, P, w% x8 j- J
2 s. O* ]- s8 L) Y6 H
    删除：将值设置为0，将数据节点推送到一个空闲节点，然后更新根节点。请注意，这个操作实际上并没有从数据结构中删除节点，因此n永远不会减少。
. j1 v5 L- m+ d
; e5 S) a: ], r! D9 h    追加：从前面提到的空闲堆栈中弹出一个节点，否则追加一个新节点，并赋值。2 F1 G; _# V8 ]* _. M

. o/ B+ t. a) h1 Y  B/ |2 b    执行过程中的算力节省9 T3 s. e; H/ v9 v$ m. s

# Q+ I% Y4 {- L3 T    因为结构中的数据并未被删除（它们只被设置为0并被推送到堆栈），所以在执行过程中可以节省一大部分的算力。我们只需要一个空闲节点堆栈列表和一个数据结构中实际值的列表。如上例所示，列表会是：[50,25,25,10,15,20,5]。使用以下等式可以轻松实现节点遍历：- n# r) N" \9 f- i: p3 l9 Z9 J

/ l$ r  x" f4 ?" s    节点i的第C个子节点：K*i+c。原理：首先必须跳过每个i之前的节点的和它们的子节点，所以是K*i；然后加上c来得到你想要的子节点。
2 b2 K2 K$ `5 }* |+ q
' F9 |; L6 Y  S6 Y- F; Z    节点i的根节点：（i-1）/K。原理：跳过多少个拥有K个子节点的节点才能到达i。
; C1 q% ~/ A( A5 s; X" X
6 ]6 t( m4 m% u6 p( B3 F    检查节点i是否是第一个/最左边的节点：（i-1）％K===0。基本原理类似于找到根节点的，当余数为0时就是第一个/最左边的节点。
  q$ j0 M( {0 |, z; A/ }+ r1 p6 S' f9 m3 M* V1 A4 K
    Kleros的实例
; Q  T# D' f# v4 h: n+ ^8 |6 [7 \. M% T: `" N+ w' L
    Kleros智能合约库的数据结构文件夹中，包括了k-ary树状数组的开源实现（每个节点的子节点数目可以自定）：https://github.com/kleros/kleros ... cts/data-structures
6 Z# C# d; h3 e2 z
. V; q# G3 _- ?3 k9 @- K% p9 n    里面包括了一个继承该功能的分类树状数组智能合约，可用于所有需要分类的智能合约。