小编Gus*_*res的帖子

我需要设计一个数据结构,它可以有效地支持对存储的(我认为合适的)数字序列的以下操作:

• 将整数添加x到i序列的第一个元素
• k在序列的末尾附加一个整数
• 删除序列的最后一个元素
• 检索序列中所有元素的平均值

例

从空序列开始 []

• 追加0([0])
• 追加5([0, 5])
• 追加6([0, 5, 6])
• 将3添加到序列中的前2个元素([3, 8, 6])
• 找回平均5.66([3, 8, 6])
• 删除最后一个元素([3, 8])
• 检索平均值5.5([3, 8])

之前的工作

我想过使用Fenwick Trees(Topcoder Editorial),但为此我需要指定Fenwick树初始化的序列的最大大小,这不一定是知道的.但是如果我有序列可以支持的最大元素数量,我可以支持这些操作,O(lg N)如果我还保存序列中所有元素的总和.

编辑:问题是Codefor的问题,我需要所有操作的子线性运行时间,因为在最坏的情况下,添加到第一个元素可能与添加到整个序列相同

我正在使用django-crispy-forms在django中呈现模型的形式.django-crispy-forms已经与Twitter Bootstrap很好地集成,并为AppendedText小部件定义了一个布局对象:

我的django中有以下型号 models.py

class Historia(models.Model):
    persona         = models.ForeignKey('Persona', 
                                  blank=False, 
                                  null=True,
                                  related_name='historias')
    fecha           = models.DateTimeField(unique=True, 
                                auto_now_add=True)
    motivo          = models.TextField()
    peso            = models.DecimalField(blank=True,
                                   max_digits=5, decimal_places=2)
    talla           = models.IntegerField(blank=True)
    tension         = models.CharField(max_length=15)
    pulso           = models.IntegerField()
    diagnostico     = models.TextField()
    tratamiento     = models.TextField()
    pendiente       = models.TextField(blank=True)

我定义以下modelform的forms.py:

class HistoriaForm(django.forms.ModelForm):
    class Meta:
        model = models.Historia

    def __init__(self, *args, **kwargs):
        super(HistoriaForm, self).__init__(*args, **kwargs)

        self.helper = FormHelper(self)
        self.helper.form_class = 'form-horizontal'
        self.helper.form_tag = True
        self.helper.form_id = …